[백준] java 4779 칸토어 집합

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

문제

이미지 출처: 백준

입력

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

풀이과정

재귀 카테고리이므로 연습 겸 상향식 대신 하향식으로 접근해보았다.

먼저 문제 예제에선 길이가 27인 하이폰을 3등분하여 가운데 부분을 모두 공백으로 바꾸고 있다.

27을 3등분하면 9이므로 10번째 하이폰부터 18번째 하이폰까지 공백으로 변경하는 것이다. 마찬가지로 총 길이가 9인 하이폰 또한 4번째 하이폰부터 6번째 하이폰까지 공백으로 변경해준다. 이런 패턴을 보고 바로 병합 정렬의 원리가 생각났는데, 병합 정렬은 배열을 가장 작은 단위로 쪼개서 인접 배열끼리 비교하고 합치고 다시 비교하고 합치는 원리를 가졌다.

병합 정렬은 배열을 쪼개는 것이 물리적으로 쪼개는 것이 아니라 논리적으로 배열의 작은 부분의 인덱스를 계산해 부분 배열만 비교한다.

다음은 자바로 작성한 풀이 코드이다.

public class Main {

    static char[] kantoa;
    // 매개변수에는 부분 배열을 구하기 위한 
    // 논리적 인덱스인 left, right
    // left는 시작 인덱스이고, right는 끝 인덱스이다.
    static void kantoa(int left, int right){
    
		// left가 right와 같거나 크다면
        // 더 이상 부분배열을 구할 수 없음
        if(left < right) {
        
			// 부분 배열 길이의 나누기 3
            // 만약 left가 0이고 right가 9라면
            // part == 3
            int part = (right + 1 - left) / 3;
            
            // part 담을 임시 변수        
            int temp = part+left;
            
            // 공백으로 바꿔 넣기 시작하는 인덱스는
            // left(시작) 인덱스 + part
            // 현재 배열의 길이가 9라고 생각해보자.
            // 3등분을 하면 part는 3이므로 left(시작) 인덱스로부터
            // part만큼 더하는 부분이 공백으로 바꾸기 시작하는 인덱스이다.
            int index = left + part;

            while (part-- > 0) {
                kantoa[index++] = ' ';
            }
			
            // 배열(하이폰)의 총 길이가 9라면 하이폰은
            // --------- 이며 최초의 kantoa 메서드가 호출되면
            // ---   --- 일 것이다.          
            // 가운데 공백으로부터 왼쪽, 오른쪽 하이폰 문자열(배열) 또한 kantoa 메서드를 호출시켜야한다.
            kantoa(left, temp - 1);
            
            // 공백이 채워지고 난 이후 인덱스와 right(끝 인덱스)
            kantoa(index, right);

        }

    }

    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String input = "";
        while( (input = br.readLine()) != null && !input.isEmpty() ){
			// 총길이
            int length = (int)Math.pow(3,Double.parseDouble(input));
			
            kantoa = new char[length];
			
            for (int i = 0; i < length; i++)
                kantoa[i] = '-';
			// 칸토어 집합 
            kantoa( 0, kantoa.length-1 );
            
            for(int i = 0; i<kantoa.length; i++)
                sb.append(kantoa[i]);
            sb.append("\n");
        }
        System.out.println(sb);
    }
}