baekjoon - 회문 (투포인터)
난이도 - gold5
시간 제한메모리
| 1 초 (추가 시간 없음) | 512 MB |
회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.
여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다.
입력
입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1 ≤ T ≤ 30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3 이상 100,000 이하이고, 영문 알파벳 소문자로만 이루어져 있다.
7
abba
summuus
xabba
xabbay
comcom
comwwmoc
comwwtmoc
출력
각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.
이렇게 문제가 있고, 간단히 말해서 앞뒤가 똑같은 문자열이면 0, 1개 만 제외 했을때 똑같으면 1, 2개 이상으로 안맞으면 2를 출력하는 문제이다.
풀이)
그러면 문제 접근을 어떻게 해야할까? 먼저 앞과 뒤가 같은지를 체크하는게 필요하다.
그렇다면 *TwoPointer Algorithm을 사용하여 앞과 뒤를 체크해야한다.
(투포인터 알고리즘으로 접근했을 때 시간복잡도가 O(n)으로 100000번에 최대 30번을 돌수있으니까 3,000,000번 이지만 1초라는 시간은 10(8)승까지 가능하다. 그렇다면 투포인터로 풀면 적절하겠다.)
앞과 뒤를 체크했을 때 같으면 1번 Pointer는 오른쪽으로 2번 Pointer는 왼쪽으로 이동하면서 체크한다.
만약 1번 Pointer가 2번 Pointer보다 커질때까지 아무런 내용이 없다면 그것은 앞뒤가 같은 문자열인 것이다. 그렇기에 0을 출력하면 되며, 그게 아니면 유사 회문인지, 둘다 회문이 아닌지 체크할 것이다.
그렇다면 유사 회문인지를 체크하려면 앞에 문자를 뺐을때의 동일문자열인지 뒤에 문자를 뺐을때의 동일문자열인지 비교를 해야한다. 그렇다면 2가지의 경우의 수 중에 동일문자열일 수록 반환 값이 낮아지니까 재귀를 사용할 수 있다.
front+1 인 상황과 back-1 인 상황을 넣어서 2가지 중에 더 작은 수를 반환하면 될 것이다. 그래서 1, 아니면 2를 반환하며 만약 무사히 한번도 안걸리고 넘어가게 되었을 때는 똑같은 문자열으로 0을 반환하면 될 것이다.
정답 1)
#include <bits/stdc++.h>
using namespace std;
int func(string str, int front, int back, bool isChance){
while(front < back){
if(str[front] == str[back]){
front++;
back--;
}else{
if(isChance){
return 2;
}
return min(func(str, front+1, back, !isChance), func(str, front, back-1, !isChance));
}
}
if(isChance){
return 1;
}
return 0;
}
int main() {
int T;
cin >> T;
while(T--){
string str;
cin >> str;
cout << func(str, 0, str.length()-1, false) << "\n";
}
return 0;
}
정답 2)
#include <bits/stdc++.h>
using namespace std;
//1, 2 판별
int func2(string str, int front, int back, bool isChance){
while(front < back){
if(str[front] == str[back]){
front++;
back--;
}else{
if(isChance){
return 2;
}
return min(func2(str, front+1, back, !isChance),func2(str, front, back-1, !isChance));
}
}
return 1;
}
//0만 판별
int func(string str, int front, int back, bool isChance){
while(front < back){
if(str[front] == str[back]){
front++;
back--;
}else{
return func2(str, front, back, isChance);
}
}
return 0;
}
int main() {
int T;
cin >> T;
while(T--){
string str;
cin >> str;
cout << func(str, 0, str.length()-1, false) << "\n";
}
return 0;
}
정답 1번은 한번에 다 푼 경우 이고, 정답 2번은 판별하는 것을 2가지로 나눠서 계산하였지만 코드적으로 훨씬 길고, 같은 게산하는 코드가 더 많이 쓰였기 때문에 정답 1번이 좀 더 코드적으로 괜찮다라고 볼 수 있을 것이다.