문제

문제 링크

재귀를 이용해서 칸토어 집합의 근사를 만들어야 하는 문제다. 이 때 전체 집합이 유한이라고 가정한다.

(칸토어 집합에 대해서 유튜브 영상도 보고 블로그도 훑어봤지만 아직 명확하게 이해하지 못했다. 나중에
다시 보려고 한다.)

코드

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

public class Main {
    static char[] charArr;

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

        String input;
        
        // 입력 끝날 때까지 루프
        while ((input = br.readLine()) != null) {
            int n = Integer.parseInt(input);
            
            // 3^n 만큼 "-" 반복
            charArr = "-".repeat((int) Math.pow(3, n)).toCharArray();

            // 완전 이진 트리의 전위 탐색 과정과 유사함
            cantor(charArr.length, 0);
            System.out.println(charArr);
        }
    }

    static void cantor(int length, int startIndex) {
        // 선의 길이가 1이 되면 재귀 종료
        if (length == 1) {
            return;
        }

        //
        int nextLength = length / 3;

        // 3등분한 가운데 문자열을 공백으로 대체
        for (int i = 0; i < nextLength; i++) {
            charArr[i + startIndex + nextLength] = ' ';
        }

        // 각각 3등분 후의 왼쪽과 오른쪽 문자열에 재귀 함수 호출
        cantor(nextLength, startIndex);
        cantor(nextLength, startIndex + 2 * nextLength);
    }
}

풀이

$n^3$개의 '-'로 이루어진 문자열을 3등분하고 그 중 가운데 문자열을 공백으로 대체해야 한다. 그리고 나머지 두 덩이의 문자열을 다시 3등분하고 가운데 문자열을 공백으로 바꾼다. 이를 연속된 '-'의 개수가 1개가 될 때까지 반복하는 것이다.

나는 이 부분에서 이진트리의 전위 탐색을 떠올렸고 그 구현 코드를 가져와서 적용했다.