[C++] 가장 긴 팰린드롬

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/12904

프로그래머스

[문제 풀이]

팰린드롬의 가장 긴게 어느정도인지 파악하는 문제이다.

슬라이딩 윈도우 방식을 살짝 이용해서 해당 문제를 풀었다.

 

1. ABBBCBA 라는 문자열이 있다고 가정을 해보자.

이때 처음과 끝이 A로 같으니 팰린드롬을 검사하자. 팰린드롬이 아니라면 마지막 index 위치를 계속해서 조정하다가 팰린드롬이 안나온다면 start 위치를 옮겨서 B부터 시작을 하자.

이와 같이 반복을 한다면 결국 BBB일때 3으로 가장 긴 문자열이 나온다.

 

2. ABCDCBA 라는 문자열이 있다.

이때 처음과 끝이 A로 같으니 팰린드롬을 검사하자. 팰린드롬이 맞다면 마지막 index를 조정할 필요 없이 바로 break를 걸어주자. end 포인트는 마지막에서부터 처음으로 이동하니 해당 팰린드롬보다 긴 팰린드롬은 존재하지 않는다.

이렇게 start만 이동시켜서 B,C,D,C,B로 시작하는 팰린드롬을 검사하고 가장 긴 팰린드롬 숫자를 반환하자.

[회고]

1. 문자열 1일때는 당연히 1이 리턴이라 생각을 했는데 abcde일때도 당연히 1이 리턴이 되어야 한다는 점을 생각 못했다. 테스트 케이스 18번이 이거 문제인데 이 때문에 시간 오래 걸림.

2. 효율성 1번을 통과할려면 index로 팰린드롬 검사를 해야한다. substr등을 구현혹은 라이브러리를 사용해서 풀면 O(n)이 걸리기 때문에 시간초과가 난다.

[코드]

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

using namespace std;

string str;

//팰린드롬 검사
bool isPalindrome(int start, int end){
    bool answer = true;
    
    int j = end;
        
    for(int i = start;i<end;i++){
        if(str[i] != str[j--]){
            answer = false;
            //false가 뜬다면 더 검사할 필요가 없으니 return 하자.
            return answer;
        }
    }
    
    return answer;
}

int solution(string s)
{
    str = s;
    int answer=1;
    
    //만일 사이즈가 1이면 1 리턴
    // if(s.size() == 1){
    //     return 1;
    // }
    
    //0부터 시작해서 마지막 글자가 같으면 팰린드롬 검사 아니면 사이즈를 줄여서 검사하자.    
    for(int i = 0;i<s.size() - 1;i++){
        int start = i;
        int end = s.size() - 1;
        
        while(start < end){
            //만일 처음과 끝이 일치하지 않는다면 사이즈를 줄이자.
            if(s[start] != s[end]){
                end--;
            }
            //처음과 끝이 일치하다면            
            else if(s[start] == s[end]){
                if(isPalindrome(start,end) == true){
                    answer = max(answer,end - start + 1);
                    //break를 하는 이유는 크기가 더 작은 것은 검사할 필요가 없기에.
                    break;
                }                
                //팰린드롬이 아니라면 크기를 줄여서 검사해보자.
                end--;
            }
        }
    }

    return answer;
}