[JAVA] 백준 25501번 : 재귀의 귀재

https://www.acmicpc.net/problem/25501
재귀 문제이다.

처음에는 아래와 같이 코드를 작성하였는데, 시간 초과가 발생하였다. 아무래도 예제 입력을 복사하고 붙여넣기 한 후 enter를 눌러야지만 코드가 돌아갔어서 그런 것 같다.

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

public class Main {
    static int cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            cnt = 0;
            String input = br.readLine();
            int result = isPalindrome(input);
            System.out.println(result + " " + cnt);
        }
        br.close();
    }

    public static int recursion(String s, int l, int r) {
        cnt ++;
        String[] arr = s.split("");
        if (l >= r) { //홀수 : 중앙에 도달(l==r), 짝수 : l은 커지고 r은 작아짐(l > r)
            return 1;
        } else if (!((arr[l]).equals(arr[r]))) {
            return 0;
        } else { //왼쪽 인덱스와 오른쪽 인덱스의 문자가 같으면
            return recursion(s, l + 1, r - 1);
        }
    }

    public static int isPalindrome(String s) {
        return recursion(s, 0, s.length() - 1);
    }
}

그래서 split 메소드를 사용하지 않고 charAt을 사용해 보았다(브론즈 문제이다 보니 초창기 코테를 풀 때 사용했었던 charAt으로 시도해 보았음). 그랬더니 시간 초과가 발생하지 않았고, split과 charAt의 차이점을 찾아보았다.

split

• 문자열을 특정 구분자로 나누어 문자열 문자열 배열 반환

1. 전체 문자열을 탐색하여 구분자를 찾음
2. 구분자를 기준으로 문자열을 잘라 배열 생성
3. 배열에 자른 문자열 저장

• 시간복잡도 : O(n) -> 문자열의 길이에 비례

charAt

• 특정 인덱스의 문자를 반환
• 인덱스를 통해 문자열의 특정 위치에 바로 접근
• 시간복잡도 : O(1)

정답 코드

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

public class Main {
    static int cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            cnt = 0;
            String input = br.readLine();
            int result = isPalindrome(input);
            System.out.println(result + " " + cnt);
        }
        br.close();
    }

    public static int recursion(String s, int l, int r) {
        cnt++;
        if (l >= r) { // 홀수: 중앙에 도달(l==r), 짝수: l은 커지고 r은 작아짐(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);
    }
}