[백준]4779: 칸토어 집합(재귀)

 

재귀 연습 문제를 풀어보았다.... 재귀는 참 어렵군,,, 코드를 보고 해석하는건 쉽지만 혼자 생각해내기는 너무 어렵다. 이 문제도 꽤나 애를 먹었다.

---

정답 코드

package reculsive;

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

public class Q4779 {
    static StringBuilder answer;

    public static void Khan(int start, int length) {
        if (length == 1) {
            return;
        }
        int newLength = length / 3;
        for (int i = start + newLength; i < start + newLength * 2; i++) {
            answer.setCharAt(i, ' ');
        }
        Khan(start, newLength);
        Khan(start + newLength * 2, newLength);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        StringBuilder sb = new StringBuilder();
        while ((str = br.readLine()) != null) {
            int N = Integer.parseInt(str);
            answer = new StringBuilder();
            for (int i = 0; i < (int) Math.pow(3, N); i++) {
                answer.append("-");
            }
            Khan(0, answer.length());
            System.out.println(answer);
        }
    }
}

 

우선 main문에 대해서 알아보겠다.

->

버퍼리더로 br.readline을 하는데 이거를 받아온 값이 null이 아닐때까지 입력을 받는다

->

STRINGBUILDER를 선언해서 초기화를 하면서 거듭제곱만큼 "-"를 저장한다.

->

KHAN함수로 들어간다.

---

 

KHAN 스펠링이 맞는지는 모르겠지만,,,, 설명을 진행해보겠수다.

 

public static void Khan(int start, int length) {
    if (length == 1) {
        return;
    }
    int newLength = length / 3;
    for (int i = start + newLength; i < start + newLength * 2; i++) {
        answer.setCharAt(i, ' ');
    }
    Khan(start, newLength);
    Khan(start + newLength * 2, newLength);
}

우선 start와 length를 받아준다. start는 시작점의 인덱스고 length는 회차의 길이이다.

->

newLength를 회차/3 해서 이번 회차로 업데이트 해준다.

->

for문에서는 i를 (시작점 + 이번 회차 길이) 부터 (시작점 + 이번회차 길이 *2) 까지 돌려준다.

결국에는 이번회차 길이 만큼 for문이 돌아간다.

가운데 부분을 공백으로 만들기 위해서 시작점을 더해주는 것이다!

->

setCharAt으로 공백으로 바꿔준다.

->

재귀로 들어가준다.

1. start, newLength가 들어간다. start가 그대로 들어간다-> 시작점이 태초와 같다,-> 0으로 고정이다-> 왼쪽 재귀!!!!

 

2. start + newLength * 2, newLength가 들어간다. start에 newLength * 2 를 더해서 들어간다. -> 시작점이 2/3 지점이다!!!! -> 시작점이 오른쪽으로 계속 업데이트가 되어야한다. -> 오른쪽 재귀!!!!!!!!!!!

 

공통: newLength로 length를 업데이트 해준다. newlength가 1이 되었다면 한개만 남은것이니 return해준다.

---

이렇게 해서 풀어봤다. 아직 재귀에 대해서 원활하게 생각이 돌아가는 것 같지 않다... 양쪽으로 나눠지는 것에 대한 회로가 덜 뚫렸달까....? 참.... 부족한 나인듯 싶다.