백준 17609번: 회문[JAVA]

백준 17609번: 회문[JAVA]

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

17609번: 회문

 

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        // 문자열의 개수를 나타내는 정수 T
        int T = Integer.parseInt(st.nextToken());
        // 문자열을담는 배열
        String[] arr = new String[T];
        String str = "";

        //문자열 입력받은 후 배열에 저장
        for (int i = 0; i < T; i++) {
            str = br.readLine();
            System.out.println(palindrome(0, str.length()- 1, str, 0));
        }
    }

    // 로직
    private static int palindrome(int start, int end, String s, int check) {
        // 문자 삭제를 2번이상 할 경우 바로 2를 반환
        if (check >= 2) {
            return 2;
        }

        // start 포인터와 end 포인터가 만나거나 지나치기 전까지 반복
        while (start < end) {
						// 같을 경우 포인터 한칸 진행
            if (s.charAt(start) == s.charAt(end)) {
                start++;
                end--;
            } else {
                // ex) abbab 같은 경우 두 경우를 비교해 더 작은 수를 반환
                return Math.min(palindrome(start + 1, end, s, check + 1), palindrome(start, end - 1, s, check + 1));
            }
        }
        return check;
    }
}

 

[정리]

투 포인터 알고리즘과 재귀함수를 활용해 풀었다. 처음엔 재귀함수 없이 while 문과 for 문으로 해결하려고 했지만 반례를 발견할 때 마다 코드가 한줄 한줄 추가되더니 스파게티 코드가 되었다. 몇시간 동안 수정 후 반례 abbab 를 만났을 때 왼쪽 문자를 제거했을 경우와 오른쪽 문자를 제거했을 경우 두 가지 모두를 생각해야 한다는 걸 깨닫고 수정하려 했지만 이미 코드는 난장판이 되어있었다. 그래서 싹 다 지우고 혼자 해결하는것을 포기하고 구글링을하며 반정도 클론코딩을 하며 해결했다. 4시간 정도 걸려서 풀었지만 막상 풀고나니 처음 시작을 제대로 했더라면 금방 풀수있는 문제였다.