[알고리즘문제] 프로그래머스 - 가장 긴 팰린드롬



펠린드롬 문제는 몇번 풀어봐서 자신있었는데 음..시간제한이 걸려서 애를 먹었습니다. 

 

1. 첫번째 방법

효율성 테스트 1번을 제외하곤 다 통과했는데, 아무래도 substr에서 많은 시간을 잡아먹은 것 같습니다. 

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

using namespace std;

bool isPalindrome(string s){
    if(s.size() % 2 == 1){ // 문자열이 홀수인 경우
        s.replace(s.size()/2,1,"");
    }
    
    int count = s.size()/2;
    
    string s1 = s.substr(0,count);
    string s2 = s.substr(count,count);
    
    reverse(s2.begin(),s2.end());
    
    return s1 == s2;
}

int solution(string s)
{
    int answer = 0;
    
    for(int i=s.size();i>=2;i--){ 
        int start = 0;
        while(start+i < s.size()){
            
            string s1 = s.substr(start,i+1);
            if(isPalindrome(s1)){
                return s1.size();
            }
            start++;
        }
    }
    return 1;
}

 

2. 두번째 방법

생각보다 시간이 오래 걸렸습니다. 은근 신경써야 하는 부분이 많더라구요.

첫번째 방법과 비교해서 가장 큰 차이점은 팰린드롬을 확인할 때, 첫번째 방법은 substr을 사용해서 새로운 문자열을 만든 반면에 두번째 방법은 문자의 index값을 사용해서 바로 비교를 해주었습니다. 

 

코드에 대해 잠시 설명을 하자면, 크게 3개의 반복문이 나옵니다.

 

left는 가장 왼쪽 인덱스, right는 가장 오른쪽 인덱스로 예를 들어 "abcdcba"에서 "cba"가 펠린드롬인 지 검사할 때 left는 "c"의 index값, right는 "a"의 index 값을 가집니다. 이후에 left++, right--하면서 값을 비교합니다.

 

1. while(len>=2)

검사해볼 펠림드롬의 문자열 길이. 예를 들어 "abcdcba"인 경우 각각 문자열이 7,6,5,4,3,2 일때를 검사해 봅니다. 만약 len일 때 펠린드롬이 발견하면 바로 len을 return 합니다. 가장 긴 펠린드롬 길이는 찾는 경우니깐요.

 

2. for(int i=0; i<=s.size() - len; i++) 

left와 right를 오른쪽으로 움직이는 횟수. "abcdcba"의 경우 len이 5이면 총 검사해야 하는 구간은 "abcdc", "bcdcb", cdcba"총 3번이 됩니다. 이때 총 3번을 반복하며 그때마다 left와 right의 위치를 오른쪽으로 한칸씩 이동해 줍니다.

 

3. while(left < right)

실제로 펠린드롬 인지 확인하는 구간입니다. left는 구간에서 왼쪽끝, right는 오른쪽 끝을 가리키고 있습니다. 이때 left++, right--하면서 각각의 s[left]값과 s[right]값이 일치하지 않으면 펠린드롬이 아니게 됩니다. 이때 flag 변수를 사용합니다.

 

 예를 들어 "abcdcba"에서 "abc"값, left = 0, right = 2인 경우

s[left]와 s[right]는 같기 때문에 left++, right--를 합니다. 근데 조건에서 left는 right보다 작아야 하기 때문에 while문을 탈출하고 len값을 return 합니다.

#include <iostream>
#include <string>
using namespace std;
int solution(string s)
{   
    int len = s.size();
    
    while(len >= 2){ // 검사해보려는 문자열의 길이. 6,5,4..2
        for(int i=0;i<=s.size() - len;i++){  // left와 right를 오른쪽으로 한칸씩 이동. 0,3 -> 1,4 -> 2,5 ...
                 int left = i;
                 int right = len+i-1;
                 bool flag = true;
            while(left < right){  // 실제로 펠린드롬인지 확인
                if(s[left] != s[right]){
                    flag = false;
                    break;
                }
                left++;
                right--;
            }
            if(flag){
                return len;
            }
        }
        len--;
    }
    return 1;
}