[백준 JAVA] 4779. 칸토어 집합

문제 링크

---

https://www.acmicpc.net/problem/4779

접근 방법

---

칸토어 집합은 길이를 3등분하여 가운데 부분을 공백으로 바꾸고, 좌우 구간에 대해서 같은 방식으로 재귀적으로 반복합니다.
n이 주어지면 전체 길이는 3^n이 되며, 재귀적으로 문자열을 가공하여 결과를 출력합니다.

소스 코드

---

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

public class Main {

    public static void makeCantor(char[] arr, int s, int len) {
        if (len == 1) {
            return;
        }

        int div = len / 3;
        for (int i = s + div; i < s + 2 * div; i++) {
            arr[i] = ' ';
        }

        makeCantor(arr, s, div);
        makeCantor(arr, s + div * 2, div);
    }

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

        while ((str = br.readLine()) != null) {
            int n = Integer.parseInt(str);
            char[] arr = new char[(int) Math.pow(3, n)];

            Arrays.fill(arr, '-');
            makeCantor(arr, 0, arr.length);
            sb.append(new String(arr)).append('\n');
        }

        System.out.print(sb);
    }
}

코드 설명

---

makeCantor(arr, s, len) 함수는 [s, s+len) 구간을 3등분하고 가운데를 공백 처리한 후 좌/우를 재귀 호출합니다.
main()에서는 EOF까지 입력을 받으며 각 줄마다 칸토어 집합을 만들어 StringBuilder에 저장 후 출력합니다.