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

가장 긴 팰린드롬

문제 링크

가장 긴 팰린드롬

분석

가장 긴 팰린드롬 부분 문자열의 길이를 구하고, 반환해야합니다.

팰린드롬(Palindrome)은 앞에서 읽으나 뒤에서 읽으나 같은 문자열을 의미합니다.
예를 들면 "abba", "racecar"등이 있습니다.

이 문제는 펠린드롬을 찾는 알고리즘을 구현하는 것과 홀수, 짝수를 구분하는 것이 중요합니다.

풀이

#include <string>
#include <algorithm>

using namespace std;

int solution(string s)
{
    int answer = 1;
    
    int n = s.size();
    
    for (int i = 0; i < n; ++i)
    {
        // 홀수 길이 팰린드롬
        int left = i;
        int right = i;

        while(left >= 0 && right < n && s[left] == s[right])
        {
            answer = max(answer, right - left + 1);
            
            --left;
            ++right;
        }
        
        // 짝수 길이 팰린드롬
        left = i;
        right = i + 1;
        
        while (left >= 0 && right < n && s[left] == s[right])
        {
            answer = max(answer, right - left + 1);
            --left;
            ++right;
        }
    }

    return answer;
}

성능 요약

시간 복잡도는 $O(n^2)$입니다.

• 문자열을 순회하는 반복문 $O(n)$
• 홀수 길이 팰린드롬 검사 $O(n)$
• 짝수 길이 팰린드롬 검사 $O(n)$
• $O(n) \times (O(n) + O(n))$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 성능

테스트 1 〉 통과 (0.01ms, 3.67MB)
테스트 2 〉 통과 (0.01ms, 3.68MB)
테스트 3 〉 통과 (0.01ms, 4.22MB)
테스트 4 〉 통과 (0.01ms, 4.37MB)
테스트 5 〉 통과 (0.01ms, 4.14MB)
테스트 6 〉 통과 (0.01ms, 4.21MB)
테스트 7 〉 통과 (0.01ms, 4.15MB)
테스트 8 〉 통과 (0.01ms, 3.68MB)
테스트 9 〉 통과 (0.01ms, 4.21MB)
테스트 10 〉 통과 (0.01ms, 4.18MB)
테스트 11 〉 통과 (0.01ms, 4.18MB)
테스트 12 〉 통과 (0.01ms, 4.21MB)
테스트 13 〉 통과 (0.01ms, 4.21MB)
테스트 14 〉 통과 (0.01ms, 4.15MB)
테스트 15 〉 통과 (0.01ms, 4.21MB)
테스트 16 〉 통과 (0.01ms, 4.22MB)
테스트 17 〉 통과 (0.01ms, 4.21MB)
테스트 18 〉 통과 (0.01ms, 4.21MB)
테스트 19 〉 통과 (0.01ms, 4.22MB)
테스트 20 〉 통과 (0.01ms, 4.21MB)
테스트 21 〉 통과 (0.01ms, 4.21MB)
테스트 22 〉 통과 (0.01ms, 4.22MB)
테스트 23 〉 통과 (0.01ms, 3.63MB)
테스트 24 〉 통과 (0.01ms, 4.16MB)

효율성 테스트

테스트 1 〉 통과 (0.04ms, 3.92MB)
테스트 2 〉 통과 (1.38ms, 3.76MB)