[알고리즘] 가장 긴 팰린드롬 / JavaScript / 프로그래머스 Lv.3

진욱·2025년 12월 22일

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

알고리즘

목록 보기

7/11

📖 문제

문제 풀러 가기

문제 설명

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

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

제한 사항

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

입출력 예

s	answer
"abcdcba"	7
"abacde"	3

입출력 예 설명

입출력 예 #1
4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

입출력 예 #2
2번째자리 'b'를 기준으로 "aba"가 팰린드롬이 되므로 3을 return합니다.

🧮 풀이 1

처음 문제를 접했을 때, 분명히 제한 시간을 초과할 것을 예상했지만 우선 "팰린드롬 찾기" 에 집중해 ~~무식하게~~ 부딪혀 보았습니다.

1️⃣ 부분 문자열 생성

두 개의 인덱스 start와 end를 활용하여 부분 문자열을 생성하고, 이 부분 문자열이 팰린드롬인지 확인합니다.

for (let start = 0; start < s.length; start++) {
	for (let end = start + 1; end <= s.length; end++) {
      	...

2️⃣ 각 문자열 처리 후 비교

부분 문자열의 길이가 홀수인지 짝수인지에 따라 부분 문자열을 다시 절반으로 나누고, 한 쪽을 뒤집은 문자열이 나머지 절반과 같은지 비교합니다. 같다면, 필요한 경우 가장 긴 팰린드롬 값을 갱신합니다.

let str = s.slice(start, end);
let len = str.length;

let [left, right] = ['', ''];
if (len % 2 === 0) {
    left = str.slice(0, parseInt(len / 2));
    right = str
      .slice(parseInt(len / 2))
      .split('')
      .reverse()
      .join('');
} else {
    left = str.slice(0, parseInt(len / 2));
    right = str
      .slice(parseInt(len / 2) + 1)
      .split('')
      .reverse()
      .join('');
}

if (left === right) answer = Math.max(answer, len);

🌕 전체 코드

전체 코드는 다음과 같습니다.

function solution(s) {
	let answer = 0;
	for (let start = 0; start < s.length; start++) {
		for (let end = start + 1; end <= s.length; end++) {
			let str = s.slice(start, end);
			let len = str.length;

			let [left, right] = ['', ''];
			if (len % 2 === 0) {
				left = str.slice(0, parseInt(len / 2));
				right = str
					.slice(parseInt(len / 2))
					.split('')
					.reverse()
					.join('');
			} else {
				left = str.slice(0, parseInt(len / 2));
				right = str
					.slice(parseInt(len / 2) + 1)
					.split('')
					.reverse()
					.join('');
			}

			if (left === right) answer = Math.max(answer, len);
		}
	}

	return answer;
}

🧪 실행결과

코드를 제출 후 채점하면 정확성 테스트는 문제 없이 통과하지만 효율성 테스트에서는 아래와 같이 시간 초과가 발생하는 것을 확인할 수 있습니다.

이유가 무엇일까요? 위 코드의 시간 복잡도를 살펴보면,

1️⃣ 첫 번째 과정에서 부분 문자열을 생성할 때 길이가 $n$ 인 문자열을 이중으로 반복하므로, $O(n^2)$ 의 시간 복잡도를 가집니다.

2️⃣ 두 번째 과정에서 각 부분 문자열을 처리할 때 약 $O(n)$ 의 시간 복잡도를 가집니다.

최종적으로 전체 코드는 $O(n^3)$ 의 시간 복잡도를 가지게 됩니다. 문자열 $s$ 의 길이가 2,500 이하의 자연수이므로, 최악의 경우 약 156억 번의 연산을 필요로 하여 제한 시간을 초과하는 상황이 발생하는 것입니다.

🧮 풀이 2

따라서 위와 같이 무작정 부분 문자열을 생성하고 팰린드롬인지 비교하는 것이 아닌 새로운 해결 방법이 필요합니다.

핵심 아이디어는 다음과 같습니다.

팰린드롬의 중심 이용하기

팰린드롬의 길이가 홀수인지 짝수인지에 따라 팰린드롬은 최대 두 가지의 중심을 가집니다.

홀수 길이 팰린드롬	짝수 길이 팰린드롬

각각의 경우에 따라 중심을 기준으로 좌우로 확장하면서 가장 긴 팰린드롬 값을 갱신하면 됩니다.

1️⃣ 중심점을 기준으로 확장

중심을 기준으로 좌우로 확장하면서 가장 긴 팰린드롬 값을 갱신하는 함수를 생성합니다.

function findPalindrome(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
        answer = Math.max(answer, right - left + 1);
        left--;
        right++;
    }
}

2️⃣ 중심점 결정

문자열을 순회하며 중심점을 정하고, 홀수인 경우 i번 째 위치부터 좌우로 확장, 짝수인 경우 i번 째 위치부터 좌측으로, i + 1번 째 위치부터 우측으로 확장하며 팰린드롬인지 확인합니다.

for (let i = 0; i < s.length; i++) {
    // 홀수 길이 탐색
    findPalindrome(i, i);

    // 짝수 길이 탐색
    findPalindrome(i, i + 1);
}

🌕 전체 코드

전체 코드는 다음과 같습니다.

function solution(s) {
	let answer = 0;

	function findPalindrome(left, right) {
		while (left >= 0 && right < s.length && s[left] === s[right]) {
			answer = Math.max(answer, right - left + 1);
			left--;
			right++;
		}
	}

	for (let i = 0; i < s.length; i++) {
		// 홀수 길이 탐색
		findPalindrome(i, i);

		// 짝수 길이 탐색
		findPalindrome(i, i + 1);
	}

	return answer;
}