[백준] 4779번: 칸토어 집합 (Java)

1. 문제설명

주어진 n에 대해 “-”가 3^n이 있는 문자열을 생성하고,
모든 선의 길이가 1일 될 때까지 문자열을 3등분하여 가운데 문자열을 공백으로 만든다.

마지막 문자열의 결과를 출력하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 128MB

 

2. 접근 방식

• 문자열을 3등분하고 모든 선이 1이 될 때까지 재귀 호출하는 함수를 사용한다.
• cantor 함수
  • 검사하려는 시작 인덱스(`s`)와 문자열 길이(`len`)를 매개변수로 받는다.
  • `len`이 1이면 종료한다.
  • `len`을 3으로 나눈 `div`를 구해,
    `s+div ~ s+div*2`에 해당하는 부분(2번째 부분)을 공백으로 변경한다.
  • 1번째, 3번째 부분을 재귀 호출한다.

 

3. 최종 코드

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

public class Main {
    static StringBuilder result; // 문자열 저장할 StringBuilder

    static void cantor(int s, int len) {
        if(len == 1) return; // 길이가 1이면 종료
        int div = len/3; // 현재 문자열 길이 3등분
        for(int i=s+div; i<s+div*2; i++) {
            // 3등분 중 2번째 부분을 공백으로 변경
            result.setCharAt(i, ' ');
        }
        cantor(s, div); // 3등분 중 1번째 부분을 재귀 호출
        cantor(s+div*2, div); // 3등분 중 3번째 부분을 재귀 호출
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while((str = br.readLine()) != null) { // 파일의 끝에서 입력을 멈춤
            int n = Integer.parseInt(str);
            result = new StringBuilder(); // 문자열 초기화
            for(int i=0; i<(int)Math.pow(3, n); i++) {
                result.append("-"); // 3^n 만큼 "-"으로 초기화
            }
            cantor(0, result.length()); // 시작인덱스, 문자열 길이로 메서드 호출
            System.out.println(result);
        }
        br.close();
    }
}

 

4. 시간복잡도

각 테스트케이스를 $t$, 각 테스트케이스의 입력값이 $n$일 때 $O(t * 3^n)$ 이다.