[프로그래머스] 가장 긴 팰린드롬 문제 풀이 (c++)

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

프로그래머스

 

문제 요약) 팰린드롬은 앞뒤로 뒤집어도 똑같은 문자열을 의미한다. 주어진 문자열의 부분 문자열 중 가장 긴 팰린드롬의 길이를 구하는 문제이다.

 

[풀이]

• 완전 탐색으로 부분 문자열을 모두 비교하는 시간복잡도는 O(N^3) 이며, 주어진 입력 S.len() <= 2,500 이기 때문에 최적화 된 방법을 찾아야한다.
• 재귀함수를 사용하면 팰린드롬을 최적화 할 수 있다. 본인은 O(N^2) 로 해결하였다.
• 두가지의 조건을 통해 팰린드롬을 구한다.
  1. S[st] == S[ed + 1] 인 경우 두개의 문자열은 같기 때문에 팰린드롬이 된다.
  2. 중앙의 모든 문자열이 동일하면서, S[st - 1] == S[ed + 1] 인 경우 [st - 1, ed + 1] 구간이 팰린드롬이 된다.
• 2번의 조건이 한번이라도 참이라면, 1번의 조건은 더이상 비교할 수 없다.
  ex) "abccba" 가 주어졌을 때, 처음 index를 2라고 가정하면,
   - b[st] == b[ed + 1] ('c' == 'c') cur = "cc"
   - b[st - 1] == b[ed + 1] ('b' == 'b') cur = "bccb" 이 다음 1번 조건을 비교하게 되면 팰린드롬이 아니게된다.
   - b[st - 1] == b[ed + 1] ('a' == 'a') cur = "abccba"

 

[코드]

#include <vector>
#include <string>
using namespace std;

int foo(string& s, int st, int ed, int ans, bool f) {
	auto cur = ans;
	if (f && ed < s.size() && s[st] == s[ed + 1])
		cur = max(foo(s, st, ed + 1, ans + 1, true), ans);

	if (st > 0 && ed + 1 < s.size() && s[st - 1] == s[ed + 1])
		cur = max(foo(s, st - 1, ed + 1, ans + 2, false), cur);

	return cur;
}

int solution(string s) {
	int answer = 1;

	for (int i = 0; i < s.size(); i++) {
		answer = max(answer, foo(s, i, i, 1, true));
	}

	return answer;
}

 

[코드 설명]

• foo 라는 재귀 함수 시그니처는 현재까지 팰린드롬인 start index 와, end index 를 받으며, 2번 조건이 한번이라도 성립했는지 확인하기 위한 flag 를 넘겨 받는다.
• array 의 out of range 를 고려하여, index 의 범위 조건을 걸고 1, 2 번의 조건을 추가하면 재귀적으로 호출했을 때 O(N^2) 에 해결된다.