[알고리즘 풀이 분석] BOJ 17609 회문

오늘 풀어본 문제는 BOJ 17609 회문 이다!
가볍게 스트링 연습문제로 하루를 시작하려 했으나 지독한 놈이었다,, ㅜ
개오래걸림 챔내..

BOJ 17609 회문

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.

여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다.

입출력

[입력]
입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1 ≤ T ≤ 30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3 이상 100,000 이하이고, 영문 알파벳 소문자로만 이루어져 있다.

[출력]
각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.

나의 풀이

뜻밖에도 여러가지 풀이 방법을 시도했던 것 같다,,

투포인터로 풀어보다가 틀렸다길래 아닌 것 같아서 재귀로 풀어보았는데 왠 메모리 초과도 뜨고,, 결국 다시 투포인터로 돌아와 블로그 글을 참고해 해결해야했다,, 아 별거 아닌데 해결을 제대로 못해서 찝찝..하다

한번의 기회를 가지고 있고 반으로 접어서 대칭인지를 확인하면 되는 문제이므로 두 포인터를 사용해야 한다고 생각했다.

두 포인터 start, end 가 가리키는 문자가 같다면 다행이지만 다르다면 그 한번을 어떻게 확인하느냐가 관건인 문제이다.

처음엔 start 를 증가시켜 확인하고 다음에 end를 한번 감소시켜 확인했는데 재귀적으로 풀었더니 메모리가 초과되었고 순차적으로 하자니 abbab 와 같은 반례를 커버하지 못했다.

abbab 를 예로 들었을 때 start를 먼저 증가시킨다면 통과하여 유사 회문으로 판단되지만 end를 먼저 감소시킨다면 통과하지 못하고 결과값 2를 반환한다.

즉, start 를 증가시킨 경우와 end를 감소시킨 경우, 두 경우중 어느 한곳에서라도 통과한다면 유사회문으로 판단해도 되는 것이다.

그냥 간단하게 두 변수 left_passed, right_passed 를 사용하였다.

left_passed 가 먼저 true 로 판명되면 바로 결과값을 반환하고 그렇지 않다면 right_passed에서 통과 되는지 한번 더 검사한다.

cpp 로 푼 다음 swift 로 풀어봤는데 동일한 코드지만 swift 에선 시간 초과가 난다,,, 흠 왜징,, 이건 더 고민 해 봐야겠다.

코드

cpp

#include <iostream>
#include <string>
#include <vector>

// boj 17609 회문, 문자열, 실버 1
using namespace std;

vector<int> answer;

int check(string str){
    int start = 0, end = str.size()-1;
    int result = 0;

    while (start<=end){
        if (str[start] == str[end]){
            start++;
            end--;
        }else{
            int left = start+1, right = end;
            bool left_pass = true;
            while (left<=right){
                if(str[left] !=  str[right]){
                    left_pass = false;
                    break;
                }
                left++;
                right--;
            }

            if (left_pass){
                result = 1;
                return result;
            }

            left = start, right = end-1;
            bool right_pass = true;
            while (left<=right){
                if (str[left] != str[right]){
                    right_pass = false;
                    break;
                }
                left++;
                right--;
            }

            if (right_pass) result = 1;
            else result = 2;

            return result;
        }
    }
    return result;
}
int main() {
    int T;
    cin>>T;

    answer.assign(T, -1);
    for (int i = 0; i < T; ++i) {
        string input;
        cin>>input;
        answer[i] = check(input);
    }

    for (int i = 0; i < T; ++i) {
        cout<<answer[i]<<"\n";
    }
    return 0;
}

swift

// boj 1477 휴게소 세우기, 이분탐색, 골드 4
import Foundation

func checkStr(_ str : String) -> Int{
    var result = 0
    var start = 0
    var end = str.count-1
    
    while(start<=end){
        if(str[str.index(str.startIndex, offsetBy: start)] == str[str.index(str.startIndex, offsetBy: end)]){
            start += 1
            end -= 1
        }else{
            var left = start+1
            var right = end
            var left_pass = true
            
            while(left<right){
                if(str[str.index(str.startIndex, offsetBy: left)] != str[str.index(str.startIndex, offsetBy: right)]){
                    left_pass = false
                    break
                }
                left += 1
                right -= 1
            }
            
            if(left_pass){
                result = 1
                return result
            }
            
            left = start
            right = end-1
            var right_pass = true
            
            while(left<right){
                if(str[str.index(str.startIndex, offsetBy: left)] != str[str.index(str.startIndex, offsetBy: right)]){
                    right_pass = false
                    break
                }
                left += 1
                right -= 1
            }
            
            if (right_pass){
                result = 1
            }else{
                result = 2
            }
            return result
                
        }
    }
    
    return result
}


var T = -1
var num = readLine()
if let n = num {
    T = Int(n)!
}

for _ in 0..<T {
    let str = readLine()!
    print(checkStr(str))
}