백준 17609 회문
문제 설명
- 팰린드롬(Palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다.
- 회문이 아닌 문자열에서 한 문자를 제거하여 회문이 만들어 지는 문자열을 유사 회문(pseudo palindrome)이라고 한다.
예를 들어, summuus의 5번째 혹은 6번째 문자 u를 제거하여 만든 문자열 summus은 유사 회문이다.
- 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 유사회문인지, 둘 다 아닌지 판단하라.
- 회문이면 0, 유사 회문이면 1, 둘 다 아니면 2를 순서대로 한 줄에 하나씩 출력하라.
입력 값
- 첫 줄에는 주어지는 문자열의 개수 T ( 1 <= T <= 30 ) 가 주어진다.
- 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다.
- 주어지는 문자열의 길이는 3 이상, 100,000 이하이고, 영문 알파벳 소문자로 이루어져 있다.
예제
문제 분석
- 이 문제는 회문인지, 유사 회문인지, 아무것도 아닌지 판단하는 문제이다.
- 기본적으로 회문인지 판단하는 방법은 양 끝점부터 같은 문자가 나오는지 판단하면 된다.
즉, 문자의 길이가 N이라 하면, N/2 만으로 회문인지 판단할 수 있다.
- 이 문제에서 가장 큰 문제는 유사 회문인지 판단하는 방법이다.
- 유사 회문인지 판단하는 가장 간단한 방법은, 한 문자를 제거하여 회문이 되는지 판단하는 것이다.
- 이 경우, 문자의 길이가 N일때 한 문자를 선택하는 경우 방법 N, 회문인지 판단하는 N/2의 경우가 존재하기 때문에
O($N^2$)의 시간복잡도가 걸린다.
- 문자열의 길이는 최대 10만이기 때문에 O($N^2$)의 시간복잡도는 불가능하다.
- 그렇답면 어떻게 해야 할까?
- 유사 회문의 특성을 살펴보면 간단하게 해결할 수 있다.
- 유사 회문이란 기존 문자열에서 한 문자를 제거한 후 회문이 되는 문자를 말한다.
- 즉, 제거해야 하는 문자가 나오기 전까지는 회문의 특성을 가지고 있고,
제거해야 하는 문자는 회문의 특성을 가지고 있지 않다는 것이다.
- 정리해 보자면,
1. 양 끝점에서 중간으로 이동하며 문자가 같은지 비교한다.
2. 중간까지 이동이 되었다면 회문이라고 판단한다.
3. 중간까지 이동 전 다른 문자가 존재하게 된다면, 해당 문자 2개를 각각 지워서 회문인지 판단한다.
4. 문자 제거 후 회문이라면 유사회문이라고 판단한다.
5. 문자 제거 후 회문이라고 판단할 수 없다면, 둘 다 아니라고 판단한다.
소스 코드
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
// https://www.acmicpc.net/problem/17609
// 회문
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(bf.readLine());
StringBuilder sb = new StringBuilder();
for(int t=0;t<T;t++){
String s = bf.readLine();
sb.append(checkPalindrome(s,0,0,s.length()-1));
sb.append("\n");
}
System.out.println(sb);
}
// start 와 last 계속 비교하여 회문인지 판단
// result 0 : 회문 / result 1 : 유사회문 / result 2 : 아무것도 아님
public static int checkPalindrome(String s,int result, int start,int last){
if(result==2){
return 2;
}
while(start<=last){
if(s.charAt(start) == s.charAt(last)){
start++;
last--;
}
else{
// 현재는 회문이 아니다 -> 하나씩 제거하여 비교해서 회문인지 판별
// 더 작은 값으로 갱신
result = Integer.min(checkPalindrome(s,result+1,start+1,last),checkPalindrome(s,result+1,start,last-1));
break;
}
}
return result;
}
}
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
[BOJ-3079] 입국심사(JAVA) (0) | 2021.10.12 |
---|---|
[BOJ-2118] 두 개의 탑(JAVA) (0) | 2021.10.11 |
[BOJ-7662] 이중 우선순위 큐(C++) (0) | 2021.09.30 |
[BOJ-5427] 불(JAVA) (0) | 2021.09.29 |
[BOJ-2157] 여행(JAVA) (0) | 2021.09.28 |
댓글