백준 17609번 : 회문

문제

17609번: 회문 (acmicpc.net)

17609번: 회문

---

아이디어

우선 가장 간단한 아이디어는 StringBuilder의 reverse와 equals만을 이용하는 풀이이다.

1. reverse한게 원본과 같으면 0 출력
2. for문을 돌면서 하나씩 삭제한 다음, reverse한게 원본과 같으면 1 출력
3. for문을 다 돌 때까지 원본과 같지 않으면 2 출력

하지만, 이렇게 하면 reverse / delete / insert 와 같은 함수를 문자열의 길이만큼 반복해줘야 하므로
시간초과가 발생한다.

해결 : 투포인터 & 재귀함수

배열을 투포인터로 돌 때 사용하는 left와 right를 이용하고,
하나의 불일치 세트가 발생했을 때 동일한 기능을 수행하는 재귀함수를 호출하여 이 문제를 해결할 수 있다.
이때, 재귀함수를 실행할 때, 이전 상태가 0이었는지, 1이었는지, 2였는지에 따라서 
재귀함수 내부에서 실행하는 내용이 조금씩 달라지므로 이런 미묘한 조건문을 잘 설계하는 것이 핵심이다.

한 글자 삭제 구현

또한, 투포인터에서 '하나를 삭제하는 것'을 어떻게 구현할지도 잘 생각해내야 한다.

빨주노초파 순서대로 비교가 이루어진다고 했을 때 left=2와 right=4에서 불일치가 발생하면,
right를 하나 더 왼쪽으로 옮기고 left는 그대로 있는 조합을 비교하고,
left를 하나 더 옮기고 right는 그대로 있는 조합을 비교하면 '하나를 삭제하는 것'을 잘 구현할 수 있다.

재귀함수 설계

처음에는 재귀함수 자체를 'left, right를 비교하는 함수'로 만들었었는데,
문제는 풀리지만 흐름이 직관적으로 보이지 않았다. 
결정적으로 불일치가 발생했음에도 계속 비교를 진행하면서 불일치 횟수를 늘려서
불일치 횟수가 통합되지 않는다는 문제가 발생했다.
e.g. 위의 그림에서 초록색 비교만 유효하게 하고 싶은데, 파란색 비교까지 고려하게 되어 불일치 수가 2가 되어버림
Math.min으로 두 불일치 횟수 중 작은 것만 고려하게 했더니 문제가 해결되었다.
=> 그래도 뭔가 깔끔 x

두번째는 재귀함수를 불일치가 발생했을 때만 호출되게 하고,
인자로 받은 left와 right가 교차되는 상황까지(=전체 원소) 비교를 하되,
중간에 불일치가 2번 이상 발생하면 바로 2를 리턴하게 만들었다.
이렇게 하면 재귀함수 호출 횟수 자체가 줄어들고, 함수의 실행 흐름도 직관적으로 이해할 수 있다.

---

코드

 

package palindromeByRecursion;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int times = Integer.parseInt(br.readLine());

        for (int i = 0; i < times; i++) {
            char[] arr = br.readLine().toCharArray();
            int l = arr.length;
            System.out.println(isPalindrome(0, arr.length - 1,arr, 0));
        }
    }

    public static int isPalindrome(int left, int right, char[]arr, int delCnt){
        while(left<right){
            if(arr[left]!=arr[right]){
                if(delCnt==0){ // 불일치가 처음 발생했을 때
                    if(isPalindrome(left+1, right, arr, 1)==0 || // 하나를 무시하고 검사 진행
                    isPalindrome(left, right-1,arr,1)==0){
                        return 1; // 이후 불일치 갯수가 0이면 1을 리턴
                    } else {
                        return 2; // 이후 불일치 갯수가 1이상이면 2를 리턴
                    }
                } else {
                    return 2; // 불일치가 1번 이상 발생했는데 또 불일치 발생하면 2를 리턴
                }
            } else { // 일치하는 경우 좌, 우 포인터를 한칸씩 이동
                left++;
                right--;
            }
        }
        return 0;
    }
}

---

알게된 것

'재귀함수를 이용해서 풀어야지!'라는 접근 까지는 좋았으나, 
`두 원소를 비교하는 재귀함수` vs `두 원소에서 시작해서 끝까지 or 조건을 만족할 때까지 비교하는 재귀함수`
둘 중에 뭐가 더 효율적인가?🤔를 고민하지 않았던 것 같다.

알고리즘을 재귀함수를 이용해서 풀이할 때
언제 호출을 하는지 / 어떤 기능을 하는지 / 무엇을 리턴할 것인지 에 따라서
다양한 재귀함수를 설계할 수 있다. (처음 떠오르는 설계가 답이 아닐 수 있다는 뜻!!)

여러가지 재귀함수를 생각해보고 가장 효율적이라 판단되는 재귀함수를 설계하는 연습을 해야겠다.