프로그래머스 - 가장 긴 팰린드롬 [C++]

 이 문제는 완전 탐색과 투 포인터를 이용한 문제이다. 일단 문자열의 최대 길이가 2500이므로, O(n^2) = 6,250,000 이 되므로 1초 안에는 가능하다. 내가 처음 생각한 알고리즘은 모든 부분 문자열에 대해서 팰린드롬인지 아닌지를 판단하고, 만약 팰린드롬이면 answer를 갱신하는 방식이었다. 거의 다 잘 작동했지만, 문제는 효율성 검사 2 에서 시간 초과가 발생한다는 것이었다. 

 

 시간 초과를 줄이기 위해서 cnt에 대한 루프를 주어진 문자열 길이부터 1까지로 줄여나가는 방향으로 하고, 만약 답을 찾으면 그 즉시 리턴하는 것이다. 약간 그리디한 방식인데, 결국 문제에서 찾아야 하는건 가장 긴 팰린드롬이므로 바로 리턴하는 것이 최적해를 낼 수 있다.

 

 여기서 주의할 점은 길이가 1인 문자열은 당연히 팰린드롬이라는 것이다. 또한 부분 문자열의 길이가 홀수냐 짝수냐에 대해 헷갈릴 수 있는데, left와 right가 같을 때에도 비교를 해주고, while의 조건식을 left <= right 로 놓으면 홀짝을 고려하지 않고도 간단히 문제를 풀 수 있다.

 

 

 

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int palindrome(string& s, int start, int end) {
    int left = start;
    int right = end - 1;
    
    while (left <= right) {
        if (s[left] == s[right]) {
            left++;
            right--;
        }
        else {
            return -1;
        }
    }
    
    return end - start;
}

int solution(string s) {
    int answer = 0;
    
    for (int cnt = s.size(); cnt >= 1; cnt--) {
        int last = s.size() - cnt;
        
        for (int i = 0; i <= last; i++) {
            int start = i;
            int end = i + cnt;
            
            int result = palindrome(s, start, end);
            
            if (result != -1) {
                return result;
            }
        }
    }

    return answer;
}