📌 문제

[4779] 칸토어 집합

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

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

1. -가 3^N개 있는 문자열에서 시작한다.

2. 문자열을 3등분 한 뒤, 가운데 문자열을 공백으로 바꾼다. 이렇게 하면, 선(문자열) 2개가 남는다.

3. 이제 각 선(문자열)을 3등분 하고, 가운데 문자열을 공백으로 바꾼다. 이 과정은 모든 선의 길이가 1일때 까지 계속 한다.
모든 선의 길이가 1이면 멈춘다. N이 주어졌을 때, 마지막 과정이 끝난 후 결과를 출력하는 프로그램을 작성하시오.

⬇️ 입력

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

⬆️ 출력

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

💡 코드

✅ n을 입력받아 크기가 3의 n제곱인 boolean 타입 배열 arr[]을 생성한 후, cantor() 메서드를 호출하여 칸토어 집합을 만들어준다.

메서드 cantor(boolean[], int, int, int)는 배열 arr[]와 시작 인덱스 start, 끝 인덱스 end, 문자열을 3등분 했을 때 한 문자열의 크기 mid를 입력받는다. boolean 타입 배열의 기본값은 false이므로, 삭제해야 할 인덱스의 요소를 true로 바꿔준다. 이 때 삭제해야 할 인덱스란 3등분의 가운데 요소로, 시작 요소로부터 한 문자열의 크기를 더한 p부터 마지막 요소로부터 한 문자열의 크기를 뺀 q까지 이다.

이후 다음 문자열을 3등분 한 후의 크기인 mid를 구하여 재귀 함수를 호출하면 된다. 이 때, cantor(arr, start, p-1, mid)는 삭제된 요소의 앞쪽을, cantor(arr, q+1, end, mid)는 삭제된 요소의 뒤쪽을 정리한다.

모든 작업이 끝나면 다시 main 메서드로 돌아와 arr[i]의 요소가 true이면 ' ' (공백)을, false이면 '-'를 출력한다. 이렇게 하면 반복할 때마다 조건식을 거쳐야 하는데, 여기서 시간을 굉장히 많이 잡아먹게 된다,,

import java.io.*;
import java.util.*;
public class Main {
	
	static int n;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		String input;
		while((input = br.readLine()) != null && !input.isEmpty()) {
			n = Integer.parseInt(input);
			int pow = (int)Math.pow(3, n);
			
			boolean[] arr = new boolean[pow];
			cantor(arr, 0, pow-1, pow/3);
			
			for(int i=0;i<pow;i++) {
				if(!arr[i]) sb.append('-');
				else sb.append(' ');
			}
			sb.append("\n");
		}
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
	
	static void cantor(boolean[] arr, int start, int end, int mid) {
		if(mid < 1) return;
		
		int p = start + mid;
		int q = end - mid;
		
		for(int i=p;i<=q;i++) {
			arr[i] = true;
		}
		mid = (end - start + 1) / 3; 
		
		cantor(arr, start, p-1, mid); // 왼쪽
		cantor(arr, q+1, end, mid); // 오른쪽
	}
}

✅ 실행 시간을 줄이기 위해 boolean 타입 대신 char 타입 배열을 사용하여 조건식을 사용하지 않고 그냥 배열을 바로 출력할 수 있도록 수정하였다! 또한, 메서드 cantor()에서 굳이 입력을 굳이 필요로 하지 않는 mid와 arr[]를 제거하여 가독성을 높였다! cantor()의 전체적인 알고리즘은 위와 동일한데, arr[]의 요소들이 Arrays.fill() 메서드를 사용하여 기본값이 -인 상태에서 삭제해야 할 인덱스의 요소만 공백값으로 바꿔줬다.

import java.io.*;
import java.util.*;
public class Main {
	
	static char[] arr;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		String input;
		while((input = br.readLine()) != null && !input.isEmpty()) {
			int n = Integer.parseInt(input);
			arr = new char[(int)Math.pow(3, n)];
			Arrays.fill(arr, '-');
			
			cantor(0, arr.length-1);
			for(int i=0;i<arr.length;i++) {
				sb.append(arr[i]);
			}
			sb.append("\n");
		}
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
	
	static void cantor(int start, int end) {
		if(start >= end) return;
		
		int mid = (end - start + 1) / 3;
		int p = start + mid;
		int q = end - mid;
		
		for(int i=p;i<=q;i++) {
			arr[i] = ' ';
		}
		
		cantor(start, p-1);
		cantor(q+1, end);
	}
}