17609번: 회문

• 문자열의 개수 T가 주어진다.
• 각 문자열에 대해 다음 세 가지 중 하나를 판별한다:
  1. 그 자체로 회문이면 0
  2. 한 문자를 삭제하면 회문이 되는 유사회문이면 1
  3. 둘 다 아니면 2
• 각 문자열에 대해 판단 결과를 한 줄에 하나씩 출력하라.
• 문자열 길이는 3 이상 100,000 이하이며, 영문 소문자로만 구성된다.
• 입력 문자열의 개수 T는 1 이상 30 이하이다.

접근

시간복잡도

100,000 길이의 문자열이 30개 들어오더라도 리니어한 O(N)알고리즘으로 충분히 시간내에 해결이 가능하다.

회문

회문 판단을 하기 가장 좋은 방법은 투 포인터로 양 끝에서 시작하여 회문이 되는지 확인하는 것.

유사회문

문제는 유사회문인데, 한글자를 삭제하고 나서 회문인지 판단이 필요하다.
다만, 투포인터가 다르게 나오면 어느 포인터에 있는 글자를 삭제해야하는지 그 상황에서는 알 방법이 없다. 따라서 앞글자를 삭제하는 경우, 뒷글자를 삭제하는 경우 모두 확인을 해야한다.

코드

반복문

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		input(in);
		solve();	
	}
	
	static int length;
	static String[] strings;
	static void input(BufferedReader in) throws IOException {
		length = Integer.parseInt(in.readLine());
		strings = new String[length];
		
		for(int i = 0; i < length; i++) {
			strings[i] = in.readLine();
		}
	}
	
	static void solve(){
		StringBuilder str = new StringBuilder();
		
		for(String line : strings) {
			int left = 0;
			int right = line.length()-1;
			
			int cnt = 0;
			
			while(left <= right) {
				char front = line.charAt(left);
				char back = line.charAt(right);
				
				if(front == back) {
					left++;
					right--;
				} else {
					if((line.charAt(left+1) == back && isPalindrome(line.substring(left+1, right+1)) || 
							front == line.charAt(right-1) && isPalindrome(line.substring(left, right))))  {
						cnt = 1;
					} else {
						cnt = 2;
					}
					break;
				}
			}
			
			str.append(cnt).append("\n");
		}
		
		System.out.println(str.toString());
	}
	
	static boolean isPalindrome(String line) {
		int left = 0;
		int right = line.length()-1;
		
		while(left <= right) {
			char front = line.charAt(left);
			char back = line.charAt(right);
			
			if(front == back) {
				left++;
				right--;
			} else {
				return false;
			}
		}
		return true;
	}
}

재귀

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		input(in);
		solve();	
	}
	
	static int length;
	static String[] strings;
	static void input(BufferedReader in) throws IOException {
		length = Integer.parseInt(in.readLine());
		strings = new String[length];
		
		for(int i = 0; i < length; i++) {
			strings[i] = in.readLine();
		}
	}
	
	static void solve(){
		StringBuilder str = new StringBuilder();
		
		for(String line : strings) {
			int cnt = isPalindrome(line, 0);
			
			str.append(cnt).append("\n");
		}
		
		System.out.println(str.toString());
	}
	
	static int isPalindrome(String line, int depth) {
		if(depth >= 2) return depth;
		
		int left = 0;
		int right = line.length()-1;
		
		while(left < right) {
			char front = line.charAt(left);
			char back = line.charAt(right);
			
			if(front == back) {
				left++;
				right--;
			} else {
				return Math.min(isPalindrome(line.substring(left+1, right+1), depth+1), isPalindrome(line.substring(left, right), depth+1));
			}
		}
		return depth;
	}
}

회고

• 반복문의 경우, 단 한번만 유사회문을 체크하면되므로 코드는 덜 깔끔하더라도 메모리 사용량은 적다.
• 재귀 방식의 경우, 문자열의 길이가 100,000라서 if(depth >= 2) return depth; 로 더 깊은 탐색을 막아두지 않으면 최악의 경우 문자열 길이만큼 탐색해버리므로 메모리 초과가 나버린다.
• 직관적인 풀이법은 반복문이겠지만, 보다 깔끔하고 유사회문 삭제횟수가 늘어나는 등에 보다 유연하게 대처할 수 있는건 재귀방식이라고 볼 수 있을 것 같다.