문제
칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다.
전체 집합이 유한이라고 가정하고, 다음과 같은 과정을 통해서 칸토어 집합의 근사를 만들어보자.
1. -가 3N개 있는 문자열에서 시작한다.
2. 문자열을 3등분 한 뒤, 가운데 문자열을 공백으로 바꾼다. 이렇게 하면, 선(문자열) 2개가 남는다.
3. 이제 각 선(문자열)을 3등분 하고, 가운데 문자열을 공백으로 바꾼다. 이 과정은 모든 선의 길이가 1일때 까지 계속 한다.
예를 들어, N=3인 경우, 길이가 27인 문자열로 시작한다.
---------------------------여기서 가운데 문자열을 공백으로 바꾼다.
--------- ---------남은 두 선의 가운데 문자열을 공백으로 바꾼다.
--- --- --- ---한번 더
- - - - - - - -모든 선의 길이가 1이면 멈춘다. N이 주어졌을 때, 마지막 과정이 끝난 후 결과를 출력하는 프로그램을 작성하시오.
입력
입력을 여러 줄로 이루어져 있다. 각 줄에 N이 주어진다. 파일의 끝에서 입력을 멈춘다. N은 0보다 크거나 같고, 12보다 작거나 같은 정수이다.
출력
입력으로 주어진 N에 대해서, 해당하는 칸토어 집합의 근사를 출력한다.
예제 입력 1
0
1
3
2
예제 출력 1
-
- -
- - - - - - - -
- - - -
EOF(End Of File)
기존의 백준 문제는 항상 입력 문장의 개수를 파악할 수 있었는데, 이번 문제는 파일의 끝에서 입력을 멈추어야 해서 당황했다. 구글링해보니 다양한 방법이 있었는데, 그 중 EOF를 사용하는 방법으로 해결했다.
EOF란, End Of File의 줄임말로, 파일의 끝을 나타낸다, 이는 사용자가 더 이상 데이터를 읽을 수 없는 지점으로, 이 곳에 도달하게 되면 빈문자열이 출력으로 반환된다.
EOF를 사용하기 위해 무한으로 반복되는 while문 안에 try와 except를 사용하여 예외 처리를 진행할 것이다.
입력이 있을 땐 try문에 있는 코드들을 실행시키고, 입력이 없을 경우 break를 통해 while 문의 반복을 멈춘다.
풀이 1 - 메모리 초과
- 분할 정복(Divide and Conquer) 알고리즘의 재귀 방식을 이용하여 해결해보려고 했다.
// [BOJ] 4779. 칸토어 집합
import java.io.*;
// public
class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
try {
int N = Integer.parseInt(br.readLine());
String answer = divideAndConquer(N);
System.out.println("answer : " + answer);
} catch (Exception e) {
break;
}
}
}
public static String divideAndConquer(int n) {
if (n == 0) return "-";
String blanks = "";
for (int i = 0 ; i < Math.pow(3, n - 1); i++) {
blanks += " ";
}
return divideAndConquer(n - 1) + blanks + divideAndConquer(n - 1);
}
}해당 풀이는 메모리 초과가 났는데, 재귀를 들어가면서 반환되는 문자열들의 길이가 3^12 = 531441, 3^11 = 177147, ... 로 메모리를 많이 사용하기 때문인 것으로 추측된다.
풀이 2 - StringBuilder 이용
Java의 String의 경우 특정 인덱스에 위치한 원소값을 수정할 수 없지만 StringBuilder를 사용하면 setCharAt 메소드를 이용하여 수정이 가능하다고 한다. 때문에 매번 새로운 객체를 생성하는 String을 사용할 때보다 메모리를 크게 줄일 수 있다.
// [BOJ] 4779. 칸토어 집합
import java.io.*;
// public
public class Main {
public static StringBuilder sb;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
try {
int N = Integer.parseInt(br.readLine());
sb = new StringBuilder();
for (int i = 0; i < (int) Math.pow(3, N); i++) {
sb.append("-");
}
divideAndConquer(0, (int) Math.pow(3, N));
System.out.println(sb);
} catch (Exception e) {
break;
}
}
}
public static void divideAndConquer(int start, int size) {
if (size == 1) return;
int newSize = size / 3;
for (int i = start + newSize; i < start + 2 * newSize; i++) {
sb.setCharAt(i, ' ');
}
divideAndConquer(start, newSize);
divideAndConquer(start + 2 * newSize, newSize);
}
}'Algorithm' 카테고리의 다른 글
| [LeetCode] 2695. Array Wrapper (0) | 2024.01.31 |
|---|---|
| [LeetCode] 2677. Chunk Array (0) | 2024.01.31 |
| [SWEA] 1230. 암호문3 (1) | 2024.01.29 |
| [SWEA] 10726. 이진수 표현 (0) | 2024.01.29 |
| [SWEA] 1288. 새로운 불면증 치료법 (0) | 2024.01.29 |