프로그래머스 - 가장 긴 팰린드롬(Level 3)/Wanna Be 컴잘알

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

코딩테스트 연습 - 가장 긴 팰린드롬 | 프로그래머스

-문제-

 

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

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

제한사항

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

---

입출력 예

s	answer
abcdcba	7
abacde	3

 

-접근-

 

1. 가장 긴 팰린드롬의 길이를 구해야하니까 len = s.length()부터 시작합니다. 팰린드롬을 발견하면 더 이상 탐색할 필요가 없습니다.

2. 팰린드롬의 최소값은 1입니다. 따라서 answer = 1로 초기화해주시면 됩니다.

3. len = s.length()에서 len을 1씩 줄여나가면서 팰린드롬을 만족하는 모든 경우를 탐색합니다.

4. c++ reverse함수를 사용하면  정확도와 효율성 2번까지 통과하지만 효율성 1에서 시간초과가 발생합니다. 아마 문자열의 순서를 뒤집고 뒤집은 문자열을 다시 비교를 하게되는데, reverse함수를 사용안하고 문자열의 문자끼리 하나씩 비교하면 바로바로 틀린게 검출되기 때문에 시간이 단축되어 시간초과가 발생안되는 것 같습니다.

 

-코드-

 

(효율성 1번 케이스 : 시간 초과) 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬

int solution(string s)
{
    int answer = 1;
    int len = s.length();
    if (len == 0)
        return 0;

    while (len>=2) {
        int start = 0;
        for (int i = 0; i <= s.length()-len; i++) {
            string cur;
            string temp;
            if (len % 2 != 0) {
                cur = s.substr(i, len/2);
                temp = s.substr(i + len/2 + 1, len/2);
                reverse(temp.begin(), temp.end());
                if (temp == cur)
                    return len/2 * 2 + 1;
            }
            else {  
                cur = s.substr(i, len/2);
                temp = s.substr(i+len/2,len/2);
                reverse(temp.begin(), temp.end());
                if (temp == cur ) {
                    return len/2 * 2;
                }
            }
        }
        len -= 1;
    }
    return answer;
}

 

(시간초과 해결 코드)

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬

int solution(string s)
{
	int answer = 1;
	int len = s.length();
	if (len == 0)
		return 0;

	while (len>=2) {
		int start = 0;
		for (int i = 0; i <= s.length()-len; i++) {
			bool flag = false;

			if (len % 2 != 0) {
				for (int k = 0; k < len / 2; k++) {
					if (s[i+k] != s[i+len / 2 * 2 - k]) {
						flag = true;
						break;
					}
				}
				if (!flag)
					return len;
			}
			else {	
				for (int k = 0; k < len / 2; k++) {
					if (s[i+k] != s[i+len / 2 * 2 -1 - k]) {
						flag = true;
						break;
					}
				}
				if (!flag)
					return len;
			}
		}
		len -= 1;
	}
	return answer;
}