[백준] 재귀 - (java) 17478번 재귀함수가 뭔가요?

 

제출1

머리가 안돌아가서 for 반복문을 이용하여 풀어봤다.

import java.io.*;

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

  static String recursiveQuestion(int depth) {
    StringBuilder sb = new StringBuilder();
    sb.append("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n");
    for (int i = 0; i < depth; i++) {
      sb.append(repeat(i));
      if (i == depth - 1)
        sb.append("____".repeat(i + 1)).append("\"재귀함수가 뭔가요?\"\n").append("____".repeat(i + 1)).append("\"재귀함수는 자기 자신을 호출하는 함수라네\"\n");
    }
    for (int j = depth; 0 <= j; j--) {
      sb.append(answer(j));
    }

    return sb.toString();
  }

  static String repeat(int depth) {
    return "____".repeat(depth) + "\"재귀함수가 뭔가요?\"\n" +
        "____".repeat(depth) + "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n" +
        "____".repeat(depth) + "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n" +
        "____".repeat(depth) + "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n";
  }

  static String answer(int depth) {
    return "____".repeat(depth) + "라고 답변하였지.\n";
  }
}

---

풀이

for문으로 찾기 위해 규칙을 찾아보았다.

 

1. "재귀함수가 뭔가요 ~ 선비가 찾아와서 물었어"는 n번(입력 된 수, 이하 depth)만큼 반복된다.

언더바가 점점 증가하므로 i는 0부터 depth - 1 까지 실행한다.

depth -1 까지 실행하는 이유는, i가 depth와 동일할 때는 반복이 아닌, 답변을 해주어야하므로 depth번만 돌리게끔 설정했다.

 

2. 반복된 횟수가 n과 동일할 때 답변을 출력해야한다. ex) 초록 네모

 

3. 1~2를 마치고 나면 "라고 답변하였지."를 depth+1번 출력한다.

답변은 언더바의 개수가 점점 줄어들기 때문에 depth에서 0까지 반복한다.

 

4. 문장 앞의 "____" 언더바는 해당 depth만큼 반복되어서 출력되어야 한다.

    ex) depth가 0일 때 언더바 미출력, 1일 때 "____" 4번, 2일 때 "________" 8번

   그러므로 Java String.repeat(반복횟수) 메서드를 통해 언더바를 depth만큼 반복해 출력한다.

---

제출2

재귀 카테고리에 걸맞게 재귀함수로 풀어봤다.

import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int depth = Integer.parseInt(br.readLine());
    System.out.print(questionRecursive(depth, 0));
  }

  static String questionRecursive(int depth, int index) {
    String depthUnderBar = "____".repeat(index);
    String answer = depthUnderBar + "\"재귀함수는 자기 자신을 호출하는 함수라네\"\n";
    String repeat =
        depthUnderBar + "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n" +
            depthUnderBar + "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n" +
            depthUnderBar + "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n";

    return (index == 0 ? "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n" : "") +
        depthUnderBar + "\"재귀함수가 뭔가요?\"\n" +
        ((index == depth) ? answer : repeat + questionRecursive(depth, index + 1)) +
        depthUnderBar + "라고 답변하였지.\n";
  }
}

띠용 재귀를 잘못 짠건지 for보다 느리네. 재귀가 for보다 모든 경우에서 더 좋다고 할 수 없으니...

 

풀이

재귀스럽게(?) 규칙을 찾아보면

1. 처음에는 "어느 한  컴공 ~ 교수님 찾아가 물었다."가 출력된다.

2. "재귀함수가 뭔가요 ~ 선비가 찾아와서 물었어" 와 "라고 답변하였지" 사이 해당 문장이 반복되어 들어간다.

3. 반복된 횟수가 n보다 1 많을 때 (n = 2일때, 3번 반복되어야함_ 위 사진의 네모 번호 참고)

 

재귀를 담당하는 메서드의 매개변수는 2가지를 넣어줬다.

depth는 입력받은 n이다. 얼만큼의 깊이만큼 반복되어줘야하는 지 비교를 위해 넣었다.

제출1에서 푼 for문과 다르게 재귀메서드에 index 변수를 넣어줬다.

 

이유는, 재귀함수에서 지금 몇번 반복되었는지 알 수가 없기 때문에 비교를 위해 index를 넣어주고,

  (첫 실행인지, n만큼 실행을 했는지 등... for에서 담당하던 i 인덱스가 없기 때문)

변경시키며 depth와 비교하여 재귀를 진행했다.

 

questionRecursive() 메서드의 return 쪽을 보자.

제일 처음 실행했다면 index가 0이기 때문에 1번 조건을 출력한다.

 

그리고 "재귀함수가 뭔가요"의 질문 다음에

실행한 횟수에 따라서 답변이 나올지 or 또 다시 재귀함수를 실행해야하는지 결정해야 되므로 if() 문을 넣어서 조건을 비교했다.

만약 index가 0이라면 아직 한번만 반복되었으므로, 다시 질문을 하고, 다음 재귀함수를 호출해야한다.

index를 1 증가시켜주는 이유는, 반복된 횟수만큼 ____ 언더바를 반복시켜줘야하므로 (반복된 횟수에 따라 언더바가 늘어남) 증가시키는 것이다.

 

index가 1일이 되고, 또 depth보다 1크지 않으므로, 기존 index 1에 다시 1을 더해서 재귀를 호출한다.

드디어 index가 2가 되었을 때(3번 반복 되었을 때) depth 2와 동일하므로

드디어 선인이 답변을 해주고 재귀를 부르지 않는다.

 

기존에 불렀던 칭구들에게 return되면 예제에 맞게 출력된다....

---

출처: https://www.acmicpc.net/problem/17478

17478번: 재귀함수가 뭔가요?