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

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

코딩테스트 연습 - 가장 긴 팰린드롬

 

[풀이방법]

1. 시작점, 끝점을 정한다.

2. 시작점~끝점으로 만든 단어에서 앞에 커서 하나 뒤에 커서 하나를 두고 하나씩 중간으로 오면서 비교를한다.

- 비교를하다가 값이 다르다면 이 단어는 팰린드롬이 아니라는 플래그를 설정한 후 break 한다

- 커서가 겹치게 되는 순간이 오면 break 한다.

3. 팰린드롬이라면 최대길이인지 판단 후, answer 보다 값이 크다면 answer을 업데이트해준다.

 

효율성 2번이 풀리지 않았었는데, 위에 이미 구한 최대길이보다 작은 단어를 탐색할 경우, 팰린드롬이라는 것을 증명해도 어차피 최대값이 될 수 없기때문에 그냥 탐색하지 않고 continue를 하도록 조건문을 걸어주었더니 통과되었다.

 

 

[전체코드]

#include <iostream>
#include <string>
using namespace std;
int solution(string s)
{
    int answer=0;
    
    for(int start=0; start<s.size(); start++){
        for(int end=start; end<s.size(); end++) {
            bool possible = true;
            if(answer > end-start+1) continue;
            
            for(int k=0; k<s.size(); k++) {
                if(start+k >= end-k) continue;
                if(s[start+k] != s[end-k]) {
                    possible = false;
                    break;
                }
            }
            
            if(possible) {
                answer = max(answer, end-start+1);
            }
        }
    }

    return answer;
}