[백준] 17609 회문 - 문자열 + 재귀 JAVA

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

17609번: 회문

코드설명

문자열과 재귀를 활용하는 문제입니다.

 

문제에서 로직입니다.

1. 투포인터를 활용합니다.

2. start ( 문자열의 시작인덱스 )와 end ( 문자열의 끝 인덱스 ) delCnt ( 현재까지 삭제한 문자의 수 ) 이렇게 3가지 매개변수를 활용하여 palindrome(int start, int end, int delCnt) 를 활용합니다.

3. str[start]와 str[end] 가 가리키는 문자가 같으면, 각 인덱스를 start는 증가방향으로, end는 감소방향으로 연산시켜서 회문 연산을 진행합니다.

4. 만약 두 문자가 다르다면,

   4-1. start + 1, end를 파라미터로 보내고, delCnt(현재까지 삭제한 문자의 수)를 1개 증가시켜서 함수를 실행합니다.

   4-2. start, end - 1 를 파라미터로 보내고, delCnt(현재까지 삭제한 문자의 수)를 1개 증가시켜서 함수를 실행합니다.

   4-3. 4-1과 4-2 에서 return 되어 온 각 함수들의 값의 min값을 갱신합니다. (이 min값은 만약 회문이라면 0으로 갱신될것이고, 1,2 와 비교하며 최소값으로 갱신됩니다. 최소값으로 갱신하는 이유는 회문일 경우 0 이 반환되고, 유사회문이라면 1이기 떄문입니다. ) 가장 작은 값인 0이라면 회문인 것 입니다.

 

문제에서 만약 회문일경우, palindrome(start + 1, end, delCnt + 1) 이 호출될일이 없으므로 그대로 delCnt == 0 인상태로 return 됩니다.

재귀의 특성을 살려서 min 값을 갱신시킨다면 풀 수 있는 문제였습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	public static int N;
	public static HashMap<String, Integer> hashmap = new HashMap<>();
	public static int answer = 0;
	public static int T;
	public static String str = "";
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	int T = Integer.parseInt(st.nextToken());
    	while(T > 0) {
    		st = new StringTokenizer(br.readLine());
    		T-=1;
    		str = st.nextToken();
    		System.out.println(palindrome(0, str.length() - 1, 0));
    	}
    	
    }
	
	//palindrome은 온전한 회문이 되기까지의 최소 삭제횟수를 Return 해주는 함수입니다.
	public static int palindrome(int start, int end, int delCnt) {
		if(delCnt >= 2) { //delCnt >= 2 인경우는, 회문이 아닌 경우이므로 2 를 출력해야합니다. 1번까지는 유사회문으로 판단됩니다.  
			return 2; 
		}
		while(start < end) {
			if(str.charAt(start) == str.charAt(end)) { //서로 같으면 회문조건 통과
				start += 1;
				end -= 1;
			}else if(str.charAt(start) != str.charAt(end)) { //서로 같지 않다면, 
				int resultFirst = palindrome(start + 1, end, delCnt + 1); //한개는 start 쪽을 1개 증가시키고
				int resultSecond = palindrome(start, end - 1, delCnt + 1); //다른 한개는 end 쪽을 1개 감소시키면서 이동시킨다.
				int result = Math.min(resultFirst, resultSecond);
				return result;
			}
		}
		
		//몇개의 레벨을 거쳐서 회문이 완성되는지 체크한다.
		return delCnt; 
	}
	
}