문제
N이 주어질 때 길이 3^N의 칸토어 집합 문자열을 출력하라. 초기 문자열은 모두 '-'이고, 가운데 1/3을 공백으로 바꾸는 과정을 재귀적으로 반복한다.
입력
여러 줄에 N이 주어진다 (EOF까지).
출력
각 N에 대해 칸토어 집합 문자열을 출력한다.
예제
| 입력 | 출력 |
|---|---|
0 1 2 | - - - - - - - |
풀이
분할 정복으로 길이 3^N인 배열의 가운데 1/3을 공백으로 바꾸고, 양쪽 1/3에 대해 재귀한다.
- 길이 3^N의 배열을 '-'로 초기화한다
- 전체 구간에서 가운데 1/3 구간을 공백으로 채운다
- 왼쪽 1/3과 오른쪽 1/3에 대해 재귀적으로 같은 과정을 반복한다
- 길이가 3 미만이면 재귀를 종료한다
핵심 아이디어: 칸토어 집합은 전형적인 분할 정복 문제로, 매 단계에서 구간을 3등분하여 가운데를 제거한다.
코드
package day449;
import java.io.*;
public class Day421BOJ4779칸토어집합 {
static int N;
static char c[];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String str;
while ((str = br.readLine()) != null) {
N = Integer.parseInt(str); // N
int cnt = (int) Math.pow(3, N);
c = new char[cnt];
for (int i = 0; i < cnt; i++)
c[i] = '-';
dfs(0, cnt);
for (int i = 0; i < cnt; i++)
bw.write(c[i]);
bw.write("\n");
bw.flush();
}
}
static void dfs(int start, int length) {
if (length < 3) {
return;
}
for (int i = start + length / 3; i < start + length / 3 * 2; i++)
c[i] = ' ';
dfs(start, length / 3);
dfs(start + length / 3 * 2, length / 3);
}
}복잡도
- 시간: O(3^N) - 전체 배열을 채움
- 공간: O(3^N)