CodingTest #28 Java 25501 (재귀의 귀재) 문제 풀이

 

출처 핀터레스트

 

 

처음 코딩 테스트 입문 때 11단계까지만 풀자 했는데.. 조금 늦었지만,

 

다 풀었다!!

 

라고 생각하는 순간 재귀와 정렬 쪽에서 문제가 추가되었다.

 

자주 문제가 추가되는 것 같긴 하다.

 

저것만 풀고 다음 단계로 넘어가자.

 

백준을 더 풀거나 프로그래머스 문제도 풀 생각이다.

 

저 11단계까지 문제가 무려 89문제나 된다.. ㅎㄷㄷ

 

아직 부족하다는 느끼지만, 더 풀어봐야 할 거 같다.

 

25501 문제는 거저 주는 느낌이 강했다.

 

코드를 살펴보자.

 

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

public class Test25501 {

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

        for(int i = 0; i < N; i++) {
            int[] values = isPalindromeArray(br.readLine());
            int isPalindrome = values[0];
            int recursionCnt = values[1];

            sb.append(isPalindrome).append(" ").append(recursionCnt).append("\n");
        }
        System.out.println(sb);
    }

    static int recursionCnt = 0;

    public static int[] recursion(String s, int l, int r){
        recursionCnt++;
        if(l >= r) {
            return new int[] {1, recursionCnt};
        }
        else if(s.charAt(l) != s.charAt(r)) {
            return new int[] {0, recursionCnt};
        }
        else return recursion(s, l+1, r-1);
    }

    public static int[] isPalindromeArray(String s){
        // recursionCnt 초기화
        recursionCnt = 0;
        return recursion(s, 0, s.length()-1);
    }
}

 

처음 문제 지문을 보면 

 

public class Main{
    public static int recursion(String s, int l, int r){
        if(l >= r) return 1;
        else if(s.charAt(l) != s.charAt(r)) return 0;
        else return recursion(s, l+1, r-1);
    }
    public static int isPalindrome(String s){
        return recursion(s, 0, s.length()-1);
    }
    public static void main(String[] args){
        System.out.println("ABBA: " + isPalindrome("ABBA"));
        System.out.println("ABC: " + isPalindrome("ABC"));
    }
}

 

 

힌트로 위와 같은 코드를 제공해준다.

 

아주 문제를 거저 준다고 볼 수 있다.

 

isPalindrome의 대한 값은 반환해주니,

 

이 recursion 메서드가 호출된 횟수만 반환해 주면 된다.

 

어떻게 넘겨줄까 하다가

 

배열에 담아서 넘겨주는 방법을 선택했다.

 

static int recursionCnt = 0;

public static int[] recursion(String s, int l, int r){
    recursionCnt++;
    if(l >= r) {
        return new int[] {1, recursionCnt};
    }
    else if(s.charAt(l) != s.charAt(r)) {
        return new int[] {0, recursionCnt};
    }
    else return recursion(s, l+1, r-1);
}

public static int[] isPalindromeArray(String s){
    // recursionCnt 초기화
    recursionCnt = 0;
    return recursion(s, 0, s.length()-1);
}

 

이런 식으로 배열에 넘겨주어 isPalindrome의 여부와

 

recursionCnt의 대한 두 값을 넘겨줄 수 있게 되었다.

 

오늘 코테 끝!