[백준] | JAVA, 자바 | 4779번 - 칸토어 집합

https://www.acmicpc.net/problem/4779

---

문제 요약 :

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

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

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

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

3. 이제 각 선(문자열)을 3등분 하고, 가운데 문자열을 공백으로 바꾼다. 이 과정은 모든 선의 길이가 1일때 까지 계속 한다.

 

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

---

문제 풀이 :

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        while ((s = br.readLine()) != null) {
            int n = Integer.parseInt(s);
            int len = (int) Math.pow(3, n);

            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < len; i++) {
                sb.append("-");
            }

            recursion(0, len, sb);
            System.out.println(sb);
        }
    }

    private static void recursion(int start, int len, StringBuilder sb) {
        if (len == 1) return;

        len /= 3;

        for (int i = start + len; i < start + 2 * len; i++) {
            sb.replace(i, i + 1, " ");
        }

        recursion(start, len, sb);
        recursion(start + 2 * len, len, sb);
    }
}

 

처음 풀었던 코드, 예제를 입력하면 출력은 맞게 나왔지만 시간 초과가 나왔다.

StringBuilder를 사용하고 replace를 쓰는 과정에서 비효율적이라 시간 초과가 나온 것 같았다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        while ((s = br.readLine()) != null) {
            int n = Integer.parseInt(s);
            int len = (int) Math.pow(3, n);

            char[] array = new char[len];
            for (int i = 0; i < len; i++) {
                array[i] = '-';
            }

            recursion(0, len, array);
            System.out.println(new String(array));
        }
    }

    private static void recursion(int start, int len, char[] array) {
        if (len == 1) return;

        len /= 3;  

        for (int i = start + len; i < start + 2 * len; i++) {
            array[i] = ' ';
        }

        recursion(start, len, array);
        recursion(start + 2 * len, len, array);
    }
}

 

1. 입력이 있을 때까지 입력받기
2. 입력받은 문자열을 int형으로 변환
3. '-'가 3의 n 제곱한 값만큼 있는 문자열을 시작하기 때문에 Math.pow를 사용하여 입력받은 숫자로 3의 n 제곱 진행하고 변수 len에 저장

4. len의 크기를 가지고 있는 char 배열 생성
5. len의 크기만큼 char 배열에 '-' 저장
6. 0, len, char 배열을 매개변수로 재귀 함수 호출
6 - 1. 호출한 재귀 함수는 만약 len의 값이 1이라면 리턴
6 - 2. len의 값에 /= 3한 값을 저장

6 - 3. i가 strat + len의 값으로 시작하고, i가 start + 2 * len 한 값보다 작을 때 for 문 동작
6 - 4. array[i]의 값을 공백으로 변경
6 - 5. 왼쪽 구간에 대한 재귀 함수 호출
6 - 6. 오른쪽 구간에 대한 재귀 함수 호출
7. 배열을 문자열로 변환 후 출력