[백준] 4779번 - 칸토어 집합 (java)

>>문제 바로가기<<

칸토어 집합의 결과물을 묻는 문제이다. 입력받은 값 n의 3^n만큼의 '-' 문자열이 존재하고, 각각의 재귀에서 가운데를 제거함을 반복하는 알고리즘이다.

import java.util.*;
import java.io.*;

class Main{

	static char[] arr;
    
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String s;
        while((s = br.readLine()) != null){
        	int length = (int) Math.pow(3, Integer.parseInt(s));
            arr = new char[length];
            
            for(int i=0; i<length; i++){
            	arr[i] = '-';
            }
            
            cantor(0, length);
            System.out.println(new String(arr));
        }
    }
    
    static void cantor(int start, int length){
    	if(length == 1){ return; } // 재귀해야 할 부분의 길이가 1이면 멈춘다.
        
        int third = length/3;	   // 재귀 대상을 3분할
        for(int i=start + third; i< start + 2 * third; i++){
        	arr[i] = ' ';
            // 3분할 후 가운데 부분을 공백으로 변경
        }
        
        cantor(start, third);		// 3분할 기준으로 왼쪽 부분 재귀
        cantor(start + 2 * third, third);	// 3분할 기준으로 오른쪽 부분 재귀
        // 이 때, 첫 번째 인자는 배열의 절대위치, 두 번째 인자는 3분할 이후의 상대길이 이다.
    }
}

맞았습니다!!