칸토어 집

좋아! 이번에는 백준 4779번 칸토어 집합 문제를 Java로 풀고, 예제 입력도 내가 정해서 넣은 뒤, 각 줄을 아주 자세하게 해설해줄게.

---

✅ 문제 설명 (요약)

칸토어 집합은 다음과 같이 만들어집니다:

1. 길이 3의 문자열: "-", "-", "-" → ---
2. 가운데 부분을 공백으로 바꿈: - -
3. 이걸 각각의 -에 대해 또 반복 → 좌, 우는 그대로, 가운데는 공백

즉, N이 커질수록 3^N 길이의 문자열이 만들어지고, 재귀적으로 중간을 계속 공백으로 만듭니다.

---

✅ 예제 입력/출력

입력	출력
0	-
1	- -
2	- - - -
3	- - - - - - - -

---

✅ 입력 예제 지정:

입력:  
3  

---

✅ Java 코드 (재귀 사용)

public class CantorSet {

    public static void main(String[] args) {
        int n = 3;  // 예제 입력: 3 (길이는 3^3 = 27)
        int length = (int) Math.pow(3, n); // 전체 길이 계산
        char[] arr = new char[length]; // 결과 담을 배열 생성

        // 먼저 모두 '-'로 채우기
        for (int i = 0; i < length; i++) {
            arr[i] = '-';
        }

        // 가운데를 비우는 작업 시작
        cantor(arr, 0, length);

        // 출력
        System.out.println(new String(arr));
    }

    public static void cantor(char[] arr, int start, int length) {
        // 기저 조건: 더 이상 나눌 수 없음
        if (length == 1) return;

        int part = length / 3;

        // 가운데 부분을 공백으로 바꾸기
        for (int i = start + part; i < start + 2 * part; i++) {
            arr[i] = ' ';
        }

        // 재귀 호출: 양쪽 나머지 구간에 대해 반복
        cantor(arr, start, part);           // 왼쪽 구간
        cantor(arr, start + 2 * part, part); // 오른쪽 구간
    }
}

---

✅ 디버깅 수준 해설

---

📍 main() 함수

int n = 3;

• 역할: 칸토어 집합의 단계를 입력받음.
• 값: n = 3이면 총 길이는 $3^3 = 27$개.

---

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

• 역할: 전체 배열의 길이 계산.
• Math.pow(3, 3) → 27.
• length = 27

---

char[] arr = new char[length];

• 역할: 결과 문자열을 담을 배열.
• arr[0] ~ arr[26] 생성됨.

---

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

• 역할: 모든 문자를 -로 초기화.
• 결과: ----------...---------- (27개)

---

📍 재귀 호출 cantor(arr, 0, 27);

---

📍 첫 호출: cantor(arr, 0, 27)

• 가운데 = arr[9] ~ arr[17] → ' '로 바꿈

for (int i = 9; i < 18; i++) {
    arr[i] = ' ';
}

상태:

0~8:    - - - - - - - - -
9~17:   공백
18~26:  - - - - - - - - -

---

왼쪽 재귀: cantor(arr, 0, 9)

• 가운데 = 3~5 → 공백
• 0~2: 유지
• 3~5: 공백
• 6~8: 유지

---

다시 왼쪽 재귀: cantor(arr, 0, 3)

• 가운데 = 1 → 공백
• 상태: arr[0]='-', arr[1]=' ', arr[2]='-'

---

마찬가지로 오른쪽도 반복:

오른쪽 재귀: cantor(arr, 6, 3)

• 가운데 = arr[7] = ' '

---

재귀적으로 이렇게 반복되며, 최종적으로 배열은 이렇게 됨:

arr = ['-','-','-',' ',' ',' ','-','-','-',' ',' ',' ',' ',' ',' ',' ',' ',' ','-','-','-',' ',' ',' ','-','-','-']

출력:

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

---

✅ 출력 결과 (n = 3)

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

---

✅ 핵심 요약

단계	동작
arr[i] = '-'	초기화
cantor(arr, start, length)	length / 3로 나누고 가운데를 공백 처리
재귀	왼쪽, 오른쪽만 반복하고 가운데는 비움

---

✅ 다른 입력 예제로 보기: cantor 함수

public static void cantor(char[] arr, int start, int length) {
    // 1. 종료 조건
    if (length == 1) return;

    // 2. 현재 길이를 3등분
    int part = length / 3;

    // 3. 가운데 부분 공백 처리
    for (int i = start + part; i < start + 2 * part; i++) {
        arr[i] = ' ';
    }

    // 4. 왼쪽과 오른쪽에 대해 재귀 호출
    cantor(arr, start, part);               // 왼쪽 구간
    cantor(arr, start + 2 * part, part);    // 오른쪽 구간
}

---

✅ 예제 세팅 (n = 2)

int n = 2;
int length = (int)Math.pow(3, n);  // 3^2 = 9
char[] arr = new char[9];

// 초기화
for (int i = 0; i < 9; i++) arr[i] = '-';

🔹 이 시점에서 arr = ['-','-','-','-','-','-','-','-','-']

---

✅ 함수 호출: cantor(arr, 0, 9)

▷ 현재 상태:

• start = 0
• length = 9
• part = 9 / 3 = 3

---

▶ Step 1: 가운데 부분 공백 처리

for (int i = 3; i < 6; i++) arr[i] = ' ';

✅ 결과 상태:

arr = ['-', '-', '-', ' ', ' ', ' ', '-', '-', '-']
          ↑    ↑    ↑
        [3]  [4]  [5]

---

▶ Step 2: 왼쪽 재귀 호출

cantor(arr, 0, 3); // 왼쪽 구간 [0~2]

---

✅ 함수 호출: cantor(arr, 0, 3)

• start = 0
• length = 3
• part = 1

---

▶ Step 1: 가운데 부분 공백

for (int i = 1; i < 2; i++) arr[i] = ' ';

✅ 상태:

arr = ['-', ' ', '-', ' ', ' ', ' ', '-', '-', '-']
          ↑
        [1]

---

▶ Step 2: 재귀 호출

cantor(arr, 0, 1); // 종료 (length == 1)
cantor(arr, 2, 1); // 종료 (length == 1)

---

✅ 돌아가서 오른쪽 재귀 호출: cantor(arr, 6, 3);

• start = 6, length = 3, part = 1

---

▶ Step 1: 가운데 부분 공백

for (int i = 7; i < 8; i++) arr[i] = ' ';

✅ 상태:

arr = ['-', ' ', '-', ' ', ' ', ' ', '-', ' ', '-']
                              ↑
                            [7]

---

▶ Step 2: 재귀 호출

cantor(arr, 6, 1); // 종료
cantor(arr, 8, 1); // 종료

---

✅ 최종 배열 상태

arr = ['-', ' ', '-', ' ', ' ', ' ', '-', ' ', '-']
        ↑    ↑    ↑        ↑    ↑
        1    3    4        7    8

📌 출력: - - - - - → 출력 시 공백 그대로 포함됨

---

✅ 시각적 흐름 요약 (n = 2)

1단계 (0~8): 전체 중간 [3~5] 제거 →  ---   ---   ---
2단계 왼쪽 (0~2): 가운데 [1] 제거 → - - 
2단계 오른쪽 (6~8): 가운데 [7] 제거 → - -

---

✅ 재귀 호출 흐름 트리

cantor(0, 9)
├─ cantor(0, 3)
│  ├─ cantor(0, 1) → return
│  └─ cantor(2, 1) → return
└─ cantor(6, 3)
   ├─ cantor(6, 1) → return
   └─ cantor(8, 1) → return

---

✅ 각 단계 요약

구간 호출	변경 위치	설명
cantor(0, 9)	[3~5]	첫 전체 가운데 제거
cantor(0, 3)	[1]	왼쪽 가운데 제거
cantor(6, 3)	[7]	오른쪽 가운데 제거

---

✅ 왜 이렇게 재귀가 잘 맞는가?

• 매번 3등분하고 가운데를 비우고, 양쪽만 다시 같은 작업을 반복
• 반복되는 구조 = 재귀에 매우 적합
• base case (length == 1)이 명확히 정의됨

---

✅ 결론

칸토어 집합의 핵심은 다음 두 가지야:

1. 매번 3등분해서 가운데는 공백으로 만든다
2. 남은 좌우 구간에 대해 똑같은 일을 재귀적으로 반복한다

---