[Java] 3단계. 재귀의 귀재 [25501번]

• 예제 입력1

5
AAA
ABBA
ABABA
ABCA
PALINDROME

• 예제 출력1

1 2
1 3
1 3
0 2
0 1

---

• 문제 접근
  • 펠린드롬 문자열이라면 1, 펠린드롬 문자열이 아니라면 0 / 재귀 함수 호출 횟수를 공백으로 한 줄에 출력하는 문제
  • 입력
    • 첫째줄 : 테스트케이스 개수 T (1<= T <= 1,000)
    • 둘째줄 ~ : 알파벳 대문자로 구성된 문자열 S
  • 출력
    •  isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수를 한 줄에 공백으로 구분하여 출력
• 문제 해결
  • 문제에서 주어진 C언어 코드를 Java 언어로 변경
  • 전역 변수 count를 선언하고, for문이 시작될 때 0으로 초기화
  • isPalindrome 함수와 recursion 함수가 종료되면 StringBuilder에 넣고 테스트케이스 개수만큼 반복
• 재귀 풀이 [메모리 : 19,048 KB / 시간 : 200 ms]

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

    int T = Integer.parseInt(br.readLine());
    for(int i = 0; i < T; i++){
        count = 0;
        String s = br.readLine();
        int result = isPalindrome(s);
        sb.append(result).append(" ").append(count).append("\n");
    }
    System.out.println(sb);
}

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

private static int recursion(String s, int left, int right) {
    count++;
    if(left >= right) return 1;
    else if(s.charAt(left) != s.charAt(right)) return 0;
    else return recursion(s, left + 1, right - 1);
}

 

• 문제점
  1. 재귀 호출이 너무 많음
     • 문자열이 길면 O(N/2)번의 재귀 호출이 발생
     • 큰 입력이 들어오면 스택 오버플로우 위험이 존재
     • 해결책 : while 문을 활용하여 반복문 기반으로 변경하면 성능이 개선
  2. 입력 크기가 크므로 BufferedWriter를 활용 가능
     • BufferedWriter를 사용하면 출력 성능이 더욱 향상 됨

• 반복문 풀이 [메모리 : 19,956 KB / 시간 : 264 ms]

public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int T = Integer.parseInt(br.readLine());
    for(int i = 0; i < T; i++){
        String s = br.readLine();
        int[] result = isPalindrome(s);
        bw.write(result[0] + " " + result[1] + "\n");
    }
    bw.flush();
    bw.close();
}

private static int[] isPalindrome(String s) {
    int count = 0;
    int left = 0, right = s.length() - 1;
    while(left <= right) {
        count++;
        if(s.charAt(left) != s.charAt(right)) return new int[]{0, count};
        left++; right--;
    }

    if(s.length() % 2 == 0) count++;
    return new int[]{1, count};
}

 

• 백준 알고리즘에서는 재귀 풀이가 더 성능이 좋게 나왔는데, 재귀 호출이 비교적 적기 때문에 그럴 수 있다는 것 같음
• 그래서 아래 문자열 길이만큼 넣고 테스트를 해보니 반복문 풀이가 더 속도적으로 빨랐고 엄청나게 긴 문자열이 들어왔을 때 StackOverFlow가 발생할 수 있다는 점도 간과할 수는 없음
• 정렬 알고리즘을 공부할 때도 재귀로 하는 것보다는 반복문으로 정렬 알고리즘을 짜는 것이 좋다고 학습하였었음
• 따라서 재귀 → 반복문으로 바꾸는 것을 항상 연습하고 염두에 둘 것

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA