[PS] BOJ17609 회문 ( string ) with JAVA

 

17609번: 회문

 

 

◎ 문제풀이

 

앞뒤 방향으로 문자열이 같으면 회문, 한 문자만 다르면 유사회문이라고 한다. 회문이면 0, 유사회문이면 1, 그외 문자열은 2를 출력하는 문제이다. 투포인터를 떠올리기는 했으나 재귀호출을 발상하지 못해 문제풀이가 어려웠다. 

 

 

 

LEFT , RIGHT를 하나씩 비교하며 나갈 것이다.

 

 

 

그럼 이렇게 서로 다른 부분을 만날 수 있다.

 

경우는 2가지가 있다. 

 

1) LEFT 포인터 문자를 제거하는 경우

2) RIGHT 포인터 문자를 제거하는 경우

 

1)인 경우와 2)인 경우를 재귀호출을 활용하여 비교로직을 계속 이어가면 된다. 서로 다른 부분이 추가로 나올 수 있기 때문이다. 추가로 나오면 유사회문이 아니므로 2, 더 이상 나오지 않으면 유사회문이므로 1을 출력하면 된다. 

 

 

◎ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//BOJ17609 회문
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        while(n-- > 0){
            String str = br.readLine();
            System.out.println(process(str,0,str.length()-1,0));
        }
    }

    public static int process(String str, int left, int right, int count){
        if(count == 2) return 2;

        while( left < right ) {
            
            // 문자가 서로 다른 경우
            if (str.charAt(left) != str.charAt(right)) {
                int leftMove = process(str,left+1,right,count+1); // 왼쪽 이동후 비교로직 재귀호출
                int rightMove = process(str,left,right-1,count+1); // 오른쪽 이동후 비교로직 재귀호출
                return Math.min(leftMove,rightMove); // 최소 비교횟수 return 
            }

            left++;
            right--;
        }
        return count;
    }
}