팰린드롬 관련 알고리즘 문제들
팰린드롬 (palindrome; 회문)
팰린드롬(palindrome; 회문)은 거꾸로 뒤집어도 자기 자신과 동일한 문자열을 말합니다. 예를 들어 ‘기러기’, ‘토마토’는 우리말 회문입니다. ‘kayak’, ‘level’같은 단어들도 회문이 됩니다.
특별한 조건이 주어지지 않은 한, 어떤 문자열이 회문인지 판단하기 위해서는 시작 값과 끝 값이 같은지, 두 번째 원소가 마지막에서 두 번째 원소와 같은지…를 모두 확인해야 합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#define LEN 5
using namespace std;
bool isPalindrome() {
/* 단어 길이의 절반을 지나고 나면 더 진행할 필요가 없습니다.
똑같은 비교를 한 번 더 하는 게 되니까요*/
for (int i=0; i<LEN/2; ++i) {
if (word[i]!=word[LEN-1-i]) {
return false;
}
return true;
}
}
// 실행해 봅시다
char *word = new char [LEN];
word = "kayak";
cout << isPlindrome(word);
>>> true
관련 문제 모음
[SWEA] 19003. 팰린드롬 문제 (D3)
문제 설명
SW Expert Academy 수록 문제입니다.
각각의 테스트케이스는 아래와 같이 길이가 N인 M개의 문자열을 입력받도록 되어 있으며, 주어지는 문자열 중 어느 것도 서로 같지 않다는 조건이 붙어 있습니다. 목표는 입력된 단어들의 전체 혹은 일부를 사용해서 만들 수 있는 가장 긴 팰린드롬의 길이를 출력하는 것입니다.
1
2
3
4
5
6
7
3 7 //길이 7인 문자열 3개 (M=3, N=7)
racecar
abcdcba
ioioioi
//이 테스트케이스에 대한 정답
7
위 테스트케이스의 경우 한 문자열의 길이는 7이고, 주어진 문자열 3개가 모두 팰린드롬입니다. 두 개 혹은 세 개 문자열을 조합해서 14 혹은 21이 가능한 팰린드롬의 최대 길이가 되지 않는가 생각할 수도 있지만, 서로 같은 문자열은 주어지지 않는다는 조건 때문에 그런 경우는 발생하지 않습니다.
1
2
3
4
5
6
2 3 //길이 3인 문자열 2개 (M=2, N=3)
abb
bba
//이 테스트케이스에 대한 정답
6
기본 테스트케이스 중 다른 하나는 주어진 문자열 중 어느 것도 팰린드롬이 아닌 경우입니다. 하지만 두 개를 합치면 팰린드롬이 되기 때문에, 이 테스트케이스에 대한 정답은 6입니다.
1
2
3
4
5
6
7
3 3
abc
ded
cba
//이 테스트케이스에 대한 정답
9
주어진 문자열 중 어떤 것들은 그 자체로는 팰린드롬이 아니지만 합쳐서 팰린드롬을 만들 수 있고, 자체로 팰릔드롬인 문자열도 함께 주어지는 경우입니다.
abc와 cba는 각각은 팰린드롬이 아니지만 두 개를 결합한 abccba는 팰린드롬입니다. 여기에 자체로 팰린드롬인 ded를 가운데 끼워 넣으면 abcdedcba도 팰린드롬이 되기 때문에, 이 테스트케이스에 대한 정답은 9입니다.
접근
팰린드롬이 아닌 어떤 문자열 A를 생각해 보면, A를 뒤집은 문자열이 테스트케이스 안에 있어야만 팰린드롬을 만들 수 있습니다. 만일 문자열에 aabbb가 있다면, 테스트케이스 안에는 반드시 bbbaa가 있어야 합니다. 그렇지 않으면 aabbb는 팰린드롬의 일부가 될 수 없습니다.
만일 어떤 테스트케이스가 둘 이상의 팰린드롬 문자열을 가지고 있다고 해도, 해당 케이스의 정답이 되는 가장 긴 팰린드롬을 만드는 데는 하나 이상의 팰린드롬을 사용할 수 없습니다. 예를 들어 caac와 bffb는 둘 다 팰린드롬이지만, 팰린드롬의 길이를 더 길게 만들기 위해서 caac와 bffb를 둘 다 사용할 수는 없습니다. 하나의 테스트케이스 안에 둘 이상의 서로 같은 문자열이 주어지지 않는다는 문제의 조건 때문에 이것이 보장됩니다.
그러므로, 다음과 같이 풀 수 있습니다.
- 주어진 문자열들을 팰린드롬인 것들의 집합(P)과 팰린드롬이 아닌 것들의 집합(NP)으로 나눈다. P에 속하는 원소의 갯수는 p라고 한다.
- NP에서 팰린드롬을 만드는 데 쓸 수 있는 것들, 즉 서로 거울상을 이루는 2개의 문자열 쌍이 몇 개나 존재하는지 계산하고 이 값을 n이라고 한다.
- 주어진 테스트케이스에서 한 문자열의 길이가 N이라면, 답은 (2×n+min(1,p))×N이다: 문자열 쌍 n개 × 2 (쌍을 이루므로) + min(1,p) (팰린드롬은 P의 원소의 개수가 자연수라면 하나만 쓸 수 있다. 팰린드롬이 없다면 쓸 수 없다.)이고 한 문자열의 길이가 N이므로.
잘못된 접근
처음에는 테스트케이스에서 주어지는 모든 문자열의 조합을 재귀 DFS 순열로 나열하고 각 경우에 수에 대해 모조리 팰린드롬인지 아닌지를 계산하려고 했습니다. 팰린드롬 판정에 $N/2$회의 비교가 필요하고 나올 수 있는 경우의 수가 $\sum _{i=1}^M{_M{P_i}}$ 이므로, 총 $(N/2)\sum _{i=1}^M{_M{P_i}}$회의 비교를 하게 되고, $M$이 커질수록 시간복잡도가 끔찍합니다. 당연히 TLE가 나왔습니다.
반면 위의 방법은 가장 나쁜 경우에도 모든 문자열이 팰린드롬이 아니어서 길이 N짜리 문자 M개를 다른 문자 M-1개와 자릿수만큼 비교하게 되는 경우입니다. 이 경우 각 문자열이 팰린드롬인지 판정하는 데 걸리는 시간을 최대로 합쳐도 시간복잡도가 $(MN/2)+MN(M-1)$이고, 만일 모든 문자열이 팰린드롬이라면 M개의 길이 N인 문자열들이 팰린드롬인지 판정하는 데 걸리는 $MN/2$ 번의 비교만 거치고 나면 답이 $N$이라는 것을 알 수 있습니다. (모든 문자열이 팰린드롬이라면 문자열 두 개 이상을 조합해서 팰린드롬을 만들 수 없습니다.)