문제 출처

단계별로 풀어보기 > 재귀 > 칸토어 집합
https://www.acmicpc.net/problem/4779

문제 설명

'-'가 3^N개 있는 문자열을 3등분 한 뒤, 가운데 문자열은 공백으로 바꾼다. 이를 모든 선의 길이가 1이 될 때까지 반복한 결과를 출력하라.

접근 방법

배열의 범위를 접근하는 방식으로 풀었다.

cantorSet 메서드는 시작 위치 start, 현재 길이 len을 파라미터로 받는다.
현재 길이 len 을 3등분하여 size를 체크한 뒤,
start + size ~ start + (2 * size) 부분을 공백으로 변형한다.
이를 아까 3등분한 좌측부분, 우측 부분 모두 적용한다.

단, 현재 길이 len이 1인 경우엔 return 하여 재귀를 종료시킨다.

import java.io.*;
import java.util.Scanner;

public class 칸토어_집합 {

    public static String[] arr;

    public static void cantorSet(int start, int len) {
        if (len==1) return;

        int size = len / 3;

        for (int i = start + size; i < start + 2 * size; i++) {
            arr[i] = " ";
        }

        cantorSet(start, size);
        cantorSet(start + 2 * size, size);
    }

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

        String input;
        while ((input = br.readLine()) != null) {
            int N = Integer.parseInt(input);
            int size = (int) Math.pow(3, N);
            arr = new String[size];

            for (int i = 0; i < size; i++) {
                arr[i] = "-";
            }

            cantorSet(0, size);

            // 출력
            for (String s : arr) {
                bw.write(s);
            }
            bw.write("\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

처음엔 시작 index를 지정하지 않아서 무한 루프에 빠졌었다.
cantorSet의 시작 index를 지정해야 우측 부분을 cantorSet할 때, 무한 루프에 빠지지 않고 len == 1 조건에 달성하여 재귀를 끝낼 수 있다.

문제푼 흔적