[백준] C/C++ 회문

오랜만에 백준 문제 글을 작성하는 것 같다.😳 

회문.. 오래 걸렸다. 처음 문제를 푸는데 안 풀려서 잠시 미뤄두고 다시 머리를 식히고 푸니 그제야 해결이 되었다.

 

요즘 구현 문제들을 푸는데 상당히 아이디어를 요구하는 방식과 반례 처리? 가 중요한 것 같다는 생각이 든다. 그리고 컨디션이 중요한 느낌..(희한하게 어쩔 때는 잘 풀리는데 안 풀리는 날에는 하나도 안 풀리는 문제 부류...🤣🤫)

 

풀이 과정을 소개해보겠다.

처음에는 재귀문을 통해서 해결하려고 했다. 

시간 초과 풀이

#include <iostream>
#include <string>
using namespace std;

string s;
int l = 0;
int r;
int flag = 0;

int check(int l, int r) {
    while (l < r) {
        if (s[l] == s[r]) {
            l++;
            r--;
            continue;
        }
        else {
            if(check(l+1, r) == 0 || check(l, r-1) == 0){
                return 1;
            }
            else{
                return 2;
            }
        }
    }
    return 0;
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> s;
        cout << check(0, s.size()-1) << endl;
        
    }
}

단순해 보여서 시간 복잡도 계산도 안 하고 무지성풀이.. 시간 초과가 나서 재귀를 사용하면 안 될 것 같다는 필을 받았다.

그래서 반복문을 이용했는데 개인적인 생각이지만 이 문제의 핵심은 아래 반례 2개를 처리하냐 인 것 같다. 그 반례 2개는 질문 검색란 맨 마지막 페이지에 있었는데 

입력 : 1 baaba 정답 : 1

입력: 1 aabab 정답: 2

이 두 반례를 충족시키면 웬만해서는 통과할 것이다. 재귀가 안되므로 if문 순서로 진행되는데 s[l+1] == s[r]이 같을 때를 먼저 비교하고 만약 아닐 때, 한번 더 s[l] == s[r-1]을 비교해야 한다. 그 코드 부분만 잘 작성해주면 통과할 것이다. *(s는 input string 변수명)

 

정답 코드

#include <iostream>
#include <string>
using namespace std;

string s;
int l = 0;
int r;
int flag = 0;
int tmp_l, tmp_r;

int check(int l, int r) {
    flag = 0;
    while (l < r) {
        if (s[l] == s[r]) {
            l++;
            r--;
            continue;
        }
        else {
            if(flag == 0 && s[l+1] == s[r]){
                tmp_l = l;
                tmp_r = r;
                l++;
                flag = 3;
                continue;
            }
            else if(flag == 0 && s[l] == s[r-1]){
                r--;
                flag = 1;
                continue;
            }
            else{
                if(flag == 3){
                    l=tmp_l;
                    r = tmp_r-1;
                    flag=1;
                }
                else{
                    flag = 2;
                    break;
                }
            }
        }
    }
    if(flag == 1 || flag == 3){
        return 1;
    }
    else if(flag == 2){
        return 2;
    }
    return 0;
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> s;
        cout << check(0, s.size()-1) << endl;
        
    }
}