백준/25501 재귀의 귀재

재귀의 귀재 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초 (추가 시간 없음)

1024 MB (추가 메모리 없음)

6514

3487

3009

55.919%

문제

정휘는 후배들이 재귀 함수를 잘 다루는 재귀의 귀재인지 알아보기 위해 재귀 함수와 관련된 문제를 출제하기로 했다.

팰린드롬이란, 앞에서부터 읽었을 때와 뒤에서부터 읽었을 때가 같은 문자열을 말한다. 팰린드롬의 예시로 AAA, ABBA, ABABA 등이 있고, 팰린드롬이 아닌 문자열의 예시로 ABCA, PALINDROME 등이 있다.

어떤 문자열이 팰린드롬인지 판별하는 문제는 재귀 함수를 이용해 쉽게 해결할 수 있다. 아래 코드의 isPalindrome 함수는 주어진 문자열이 팰린드롬이면 1, 팰린드롬이 아니면 0을 반환하는 함수다.

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 함수를 이용하여 어떤 문자열이 팰린드롬인지 여부를 판단하려고 한다.

구체적으로는, 문자열 S$S$를 isPalindrome 함수의 인자로 전달하여 팰린드롬 여부를 반환값으로 알아낼 것이다. 더불어 판별하는 과정에서 recursion 함수를 몇 번 호출하는지 셀 것이다.

정휘를 따라 여러분도 함수의 반환값과 recursion 함수의 호출 횟수를 구해보자.

입력

첫째 줄에 테스트케이스의 개수 T$T$가 주어진다. (1≤T≤1000$1 \leq T \leq 1\,000$)

둘째 줄부터 T$T$개의 줄에 알파벳 대문자로 구성된 문자열 S$S$가 주어진다. (1≤|S|≤1000$1 \leq \vert S\vert \leq 1\,000$)

출력

각 테스트케이스마다, isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수를 한 줄에 공백으로 구분하여 출력한다.

예제 입력 1 복사

5
AAA
ABBA
ABABA
ABCA
PALINDROME

예제 출력 1 복사

1 2
1 3
1 3
0 2
0 1

---

풀이

주어진 재귀함수를 좀 수정하면 되는 문제

recursion 함수가 실행될때마다 카운팅을 해주면된다.

 

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String input = br.readLine();
            int[] getResult = isPalindrome(input);
            bw.write(getResult[0]+ " "+getResult[1]+"\n");
        }

        bw.flush();
        bw.close();

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

    }
    public static int[] isPalindrome(String s){
        int[] result = new int[2];
        result[1] = 1;
        return recursion(s, 0, s.length()-1,result);
    }


}

 

다른사람풀이

1. 카운팅할 변수를 static으로 전역변수로 선언해서 recursion 내부에 카운트를 증가시키는 코드를 넣어

카운팅을 얻는다. 

더 깔끔해 보인다.

다시 수정해보자.

 

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int result;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String input = br.readLine();
            bw.write(isPalindrome(input)+ " "+result+"\n");
            result=0;
        }

        bw.flush();
        bw.close();

    }
    public static int recursion(String s, int l, int r){
        result++;
        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);
    }


}

result를 전역변수로 빼고 , recursion 시작할떄 result값을 증가시킨다 ( result는 카운팅 변수)

하나의 문자열을 isPalindrome을 실행했으면 전역변수 result의값을 0으로 다시 초기화해준다.

 

정답처리됨.