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

이 글은 읽는데 약 5분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

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

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

  1. -가 3N개 있는 문자열에서 시작한다.
  2. 문자열을 3등분 한 뒤, 가운데 문자열을 공백으로 바꾼다. 이렇게 하면, 선(문자열) 2개가 남는다.
  3. 이제 각 선(문자열)을 3등분 하고, 가운데 문자열을 공백으로 바꾼다. 이 과정은 모든 선의 길이가 1일때 까지 계속 한다.

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

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

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

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

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

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

한번 더

- -   - -         - -   - -

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

입력

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

출력

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

풀이

다른 방법도 있겠지만 나는 재귀로 풀겠다. 참고로 이 문제는 단계별로 풀어보기의 재귀 단계에 속하기도 한다.

코드를 재귀로 짜면서 대략적으로 돌아가는 방식은 쉽게 세웠다. 문제는 각 단계에서 제거해야 하는 부분의 인덱스를 계산하는게 머리가 좀 아팠다.

대략적인 작동 방식은 입력받은 N을 이용해서 길이가 3N인 boolean 배열을 생성 후 모두 true로 초기화 한다. 이 배열을 canto라는 함수에 배열, 배열의 시작 인덱스, 배열의 길이, 단계를 넘겨준다.

나는 앞서 만든 하나의 배열을 계속 넘겨주고, 각 단계에서 제거할 부분의 시작과 끝 인덱스를 계산해서 배열에 접근해 그 부분만 false로 값을 변경하는 식으로 했다. 어차피 배열은 매개변수로 넘겨서 수정해도 원본이 수정되므로 재귀를 마친 배열을 순회하며 true면 -를 false면 공백을 출력하는 식으로 하였다.

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

    String input = "";

    // EOF 또는 입력이 공백일 때 까지 입력 받는다. 공백도 구분하는 이유는 IDE에서
    // 그냥 입력하면 EOF를 인식시키지 못하기 때문
    // 자세한 것은 https://yuria.dev/post/397 참고
    while((input = br.readLine()) != null && !input.isEmpty()) {
        // 길이가 3^N인 boolean 배열 생성 후 값을 true로 초기화
        int N = Integer.parseInt(input);
        boolean[] arr = new boolean[(int)Math.pow(3, N)];
        for(int i=0; i<arr.length; i++){
            arr[i] = true;
        }

        canto(arr, 0, arr.length, N);  // 칸토어 집합 만들기.

        // 만들어진 배열을 순회하며 값의 여부에 따라 대시 또는 공백 출력
        for(int i=0; i<arr.length; i++){
            if(arr[i]){
                sb.append("-");
            }else{
                sb.append(" ");
            }
        }

        sb.append("\n");  // 각 케이스의 출력은 줄바꿈으로 구분함
    }

    System.out.println(sb.toString());
    br.close();
}

// a=처리할 배열의 시작 인덱스
// b=처리할 배열의 길이
// s=공백으로 치환할 부분의 시작 인덱스
// e=공백으로 치환할 부분의 끝 인덱스
public static void canto(boolean[] arr, int a, int b, int n){
    if(n != 0){  // 단계가 0이 되면 더이상 재귀 호출하지 않는다.
        int s = (b / 3) + a;
        int e = s + (b / 3) - 1;

        // 계산된 시작 인덱스부터 끝 인덱스 까지 false로 값 변경
        for(int i=s; i<=e; i++) arr[i] = false;

        // 단계는 n-1을 한다.
        canto(arr, a, (int)Math.pow(3, n-1), n-1);  // 앞 부분만 다시 재귀호출
        canto(arr, e+1, (int)Math.pow(3, n-1), n-1);  // 뒷 부분만 다시 재귀호출
    }
}

댓글