[devmoon]백준 - 17609 (Java) 회문

https://www.acmicpc.net/problem/17609

17609번: 회문

1. 유형

문자열

 

2. 시뮬레이션

 

• 투포인터 사용
• 두 문자가 다른 경우 왼쪽을 삭제하는 경우와, 오른쪽을 삭제하는 경우가 존재
• 두 경우를 모두 탐색하기 위해 재귀사용

3. 코드

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

public class Main {
	static String s;
	static int answer;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		int T = stoi(st.nextToken());
		while (T-- > 0) {
			st = new StringTokenizer(in.readLine());
			s = st.nextToken();
			System.out.println(solve(s, 0, s.length()-1, 0));
		}
	}

	static int solve(String s, int leftpos, int rightpos, int cnt) {
		if (cnt == 2) {
			return 2;
		}
		int ret = cnt;
		while (leftpos < rightpos) {
			if (s.charAt(leftpos) != s.charAt(rightpos)) {
				int leftvalue = solve(s, leftpos + 1, rightpos, cnt + 1);
				int rightvalue = solve(s, leftpos, rightpos - 1, cnt + 1);
				ret = Math.min(leftvalue, rightvalue);
				break;
			}
			leftpos++;
			rightpos--;
		}
		return ret;
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}
// summuus에서 맞지 않는 부분이 나오면 
// 왼쪽을 삭제하는 경우, 오른쪽을 삭제하는 경우 두가지
// 재귀사용, 한번 다른경우 또 다른 경우가 나오면 return 2를 한다.
// 두 문자가 다르면 재귀를 사용해서 반복문 break