[ 백준 4779번 문제 ] 칸토어 집합 - JAVA

이번에는 백준 4779번 문제를 통해 분할 정복의 개념을 다져보자.

칸토어 집합이란 간략히 설명하면
세 개로 분할하여 가운데를 제거해 나가는 작업을 반복하여 결과를 얻는 집합이다.

두 개로 나누었던 병합 정렬을 활용하면 풀어낼 수 있다.

[ 알고리즘 ] 병합 정렬 - JAVA

---

문제 핵심

• 3의 N제곱 길이 만큼의 '-'가 반복된 문자열
• 3등분 하여 가운데를 공백으로 바꾼다.
  • 이 과정을 선의 길이가 1일 때 까지 반복

풀이 과정

합병 정렬을 이용하여 재귀를 통해 3등분 하여 처리한다.

반환 조건은 길이가 1일 때 반환한다.

핵심 코드

1. 길이가 1일 때 반환한다.
2. 크기를 3등분 한다.
3. 중간지점 부분을 모두 공백으로 바꾼다.
   1. 시작점 + 크기 = 중간지점의 시작점
   2. 시작점 + ( 2 * 크기 ) = 세번째 지점 시작점
4. 왼쪽 부분 재귀 실행
5. 오른쪽 부분 재귀 실행

private static void can(char[] arr, int start, int size) {
    if(size <= 1 ) {
        return;
    }

    int onePerThird = size / 3;

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

    can(arr, start, onePerThird);
    can(arr, start + 2 * onePerThird, onePerThird);
}

 

합병 정렬만 활용한다면 바로 풀 수 있는 쉬운 문제이다.
분할하여 재귀방식으로 풀어나가는 문제로 길이만 유의하여 코드를 작성하면 되겠다.

전체 코드

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

public class Main {

    private static void can(char[] arr, int start, int size) {
        if(size <= 1 ) {
            return;
        }

        int onePerThird = size / 3;

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

        can(arr, start, onePerThird);
        can(arr, start + 2 * onePerThird, onePerThird);
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        while (true) {
            String input = br.readLine();
            if (input == null || input.isBlank()) {
                break;
            }

            int n = Integer.parseInt(input);
            if(n == 0) {
                stringBuilder.append("-\n");
                continue;
            }

            int size = (int) Math.pow(3, n);

            char[] result = new char[size];

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

            can(result,0, size);
            stringBuilder.append(result).append('\n');
        }

        System.out.println(stringBuilder);
    }
}