프로그래머스 가장 긴 팰린드롬 c++ (문자열)

문제 설명

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

 

제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

---

입출력 예

 

입출력 예 설명

입출력 예 #1
4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

입출력 예 #2
2번째자리 'b'를 기준으로 "aba"가 팰린드롬이 되므로 3을 return합니다.

풀이

'프로그래머스 / 연습문제 / 가장 긴 팰린드롬'으로 분류되어 있는 문제이다.

 

주요 로직은 다음과 같다.

 

1. left가 0이고 right가 s.length()-1일 때 s[left]와 s[right]가 같다면 s[left]와 s[right]가 달라질 때까지 left를 1씩 증가시키고, right를 1씩 감소시키며 비교한 후, left가 right보다 크거나 같아진다면 검사를 종료한다.

 

2. 만약 1번 과정에서 left와 right가 같았던 적이 없다면 left는 0으로 냅두고 right만 1씩 감소시키며 비교한다.

//1번 과정에서 left와 right가 같았던 적이 있다면 이미 하나의 팰린드롬을 찾은 것이며, right는 감소했기 때문에

  가장 긴 팰린드롬을 찾는 이 문제에선 더 이상 탐색할 필요가 없다.

3. right가 left인 0이 되었다면 이제 left를 1 증가시키고 다시 right를 s.length()-1로 둬서 left가 s.length()-1일 때까지

  1,2의 과정을 반복한다.

 

만약 2번 과정에서 left와 right가 같았던 적이 있음에도 계속 검사하면 효율성 검사에서 시간 초과가 뜬다.

 

코드

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

using namespace std;
int solution(string s)
{
    int answer=0;
    vector<int> ans(s.length());

    for(int i=0; i<s.length();i++){
        
        for(int j=s.length()-1; j>=0; j--){
            int right =j;
            int cnt=0;
            int left=i;
            bool isFinish=false;
            while(s[left]==s[right]){
                cnt+=2;
                left++;
                right--;
                if(left==right){
                    answer = max(answer,cnt+1);
                    isFinish=true;
                    break;
                }
                else if(left>right){
                    if(cnt==2)
                        cnt--;
                    answer = max(answer,cnt);
                    isFinish=true;
                    break;
                }
            }
            if(isFinish)
                break;
        }
        
    }
        
    

    return answer;
}