프로그래머스 - 가장 긴 팰린드롬(C++)

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/12904

문제 난이도

Level 3

문제 접근법

substr을 사용하거나 비교하기 위해 reverse혹은 일일이 뒤집어 비교하기 위해 함수로 빼낸다면 효율성 1번에서 시간초과가 난다.
그래서 length 를 가장 큰 길이 = string size로 정하고 시작한다. 시작점은 항상 i=0부터 시작해서 끝과 끝에서 비교를 한다. flag를 세우고 맞을 때는 바로 return length를 한다.(최대값이기 때문)
그리고 string 범위는 1부터이기 때문에 기본으로 return 하는 값은 1로 설정한다.

통과 코드

#include <iostream>
#include <string>

using namespace std;


int solution(string s)
{
	int answer = 1;
	int len = s.size();
    	while(len>=2){
        	for(int i=0; i<=s.size()-len; i++){
            	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 answer;
}

피드백

처음에 풀었을 때, 효율성 1번만 시간 초과해서 삽질 꽤나 했다. 삽질 할 수록 정확성도 틀리고 효율성에서 넘어갈 기미가 안 보이길래 다른 코드를 참고하게 됐다.