[BOJ] 4779. 칸토어 집합

문제

칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다.

전체 집합이 유한이라고 가정하고, 다음과 같은 과정을 통해서 칸토어 집합의 근사를 만들어보자.

1. -가 3N개 있는 문자열에서 시작한다.

2. 문자열을 3등분 한 뒤, 가운데 문자열을 공백으로 바꾼다. 이렇게 하면, 선(문자열) 2개가 남는다.

3. 이제 각 선(문자열)을 3등분 하고, 가운데 문자열을 공백으로 바꾼다. 이 과정은 모든 선의 길이가 1일때 까지 계속 한다.

예를 들어, N=3인 경우, 길이가 27인 문자열로 시작한다.

---------------------------

여기서 가운데 문자열을 공백으로 바꾼다.

---------         ---------

남은 두 선의 가운데 문자열을 공백으로 바꾼다.

---   ---         ---   ---

한번 더

- -   - -         - -   - -

모든 선의 길이가 1이면 멈춘다. N이 주어졌을 때, 마지막 과정이 끝난 후 결과를 출력하는 프로그램을 작성하시오.

입력

입력을 여러 줄로 이루어져 있다. 각 줄에 N이 주어진다. 파일의 끝에서 입력을 멈춘다. N은 0보다 크거나 같고, 12보다 작거나 같은 정수이다.

출력

입력으로 주어진 N에 대해서, 해당하는 칸토어 집합의 근사를 출력한다.

 

예제 입력 1

0
1
3
2

예제 출력 1

-
- -
- -   - -         - -   - -
- -   - -

 

EOF(End Of File)

기존의 백준 문제는 항상 입력 문장의 개수를 파악할 수 있었는데, 이번 문제는 파일의 끝에서 입력을 멈추어야 해서 당황했다. 구글링해보니 다양한 방법이 있었는데, 그 중 EOF를 사용하는 방법으로 해결했다.

 

EOF란, End Of File의 줄임말로, 파일의 끝을 나타낸다, 이는 사용자가 더 이상 데이터를 읽을 수 없는 지점으로, 이 곳에 도달하게 되면 빈문자열이 출력으로 반환된다.

EOF를 사용하기 위해 무한으로 반복되는 while문 안에 try와 except를 사용하여 예외 처리를 진행할 것이다.

입력이 있을 땐 try문에 있는 코드들을 실행시키고, 입력이 없을 경우 break를 통해 while 문의 반복을 멈춘다.

 

풀이 1 - 메모리 초과

- 분할 정복(Divide and Conquer) 알고리즘의 재귀 방식을 이용하여 해결해보려고 했다.

// [BOJ] 4779. 칸토어 집합

import java.io.*;

// public
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            try {
                int N = Integer.parseInt(br.readLine());
                String answer = divideAndConquer(N);

                System.out.println("answer : " + answer);
            } catch (Exception e) {
                break;
            }
        }
    }

    public static String divideAndConquer(int n) {
        if (n == 0) return "-";

        String blanks = "";
        for (int i = 0 ; i < Math.pow(3, n - 1); i++) {
            blanks += " ";
        }

        return divideAndConquer(n - 1) + blanks + divideAndConquer(n - 1);
    }
}

해당 풀이는 메모리 초과가 났는데, 재귀를 들어가면서 반환되는 문자열들의 길이가 3^12 = 531441, 3^11 = 177147, ... 로 메모리를 많이 사용하기 때문인 것으로 추측된다.

 

풀이 2 - StringBuilder 이용

Java의 String의 경우 특정 인덱스에 위치한 원소값을 수정할 수 없지만 StringBuilder를 사용하면 setCharAt 메소드를 이용하여 수정이 가능하다고 한다. 때문에 매번 새로운 객체를 생성하는 String을 사용할 때보다 메모리를 크게 줄일 수 있다.

// [BOJ] 4779. 칸토어 집합

import java.io.*;

// public
public class Main {
    public static StringBuilder sb;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true) {
            try {
                int N = Integer.parseInt(br.readLine());
                sb = new StringBuilder();
                for (int i = 0; i < (int) Math.pow(3, N); i++) {
                    sb.append("-");
                }

                divideAndConquer(0, (int) Math.pow(3, N));

                System.out.println(sb);
            } catch (Exception e) {
                break;
            }
        }
    }

    public static void divideAndConquer(int start, int size) {
        if (size == 1) return;

        int newSize = size / 3;
        for (int i = start + newSize; i < start + 2 * newSize; i++) {
            sb.setCharAt(i, ' ');
        }

        divideAndConquer(start, newSize);
        divideAndConquer(start + 2 * newSize, newSize);
    }
}