문제 번호 27433번 : 칸토어 집합 - JAVA [자바](파일의 끝에서 입력을 멈춘다.)

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

4779번: 칸토어 집합

 

문제 설명

 

재귀를 이용하여 '-'라는 문자열을 해당 규칙에 맞게 출력하는 문제입니다.

총 3의 n승의 문자가 출력되고 3을 기준으로 나눠 중간 문자열은 빈값으로 출력해야 합니다. 

 

문제 풀이

 

백준 단계별 문제가 계속 변하면서 더 어려운 문제를 먼저 풀었습니다.

https://kkungchan.tistory.com/303

문제 번호 2447번 : 별 찍기 - JAVA [자바]

다음 문제가 지금 문제의 상위 호환 문제인 거 같습니다. 위에 문제를 정확히 이해하신 분들은 지금 문제를 푸는데 어려움이 없으실 겁니다.

 

이 문제 역시 배열로 접근합니다. 일단 3의 배수만큼 배열이 있으면 그 배열에 원하는 칸에 빈칸, 원하는 칸에는 "-"를 넣을 수 있으니 구현하는데 좀 더 편할 것입니다.

그럼 대충 main 함수 쪽은 그림이 그려집니다. 배열을 N의 3 제곱으로 만들고 재귀 함수를 만들어 배열을 완성한 후에 그 배열을 출력해 주면 됩니다.

근데 문제에서 "파일의 끝에서 입력을 멈춘다."라는 말이 있습니다. 입력을 여러 개 받는 건 알겠는데 이건 어떤 뜻일까요?(저도 이것 때문에 처음에 당황했습니다.) 알아보니 백준 문제에서 입력을 파일 형식으로 채점하도록 되어 있는 것들이 있으면 저런 식으로 문제를 준다고 합니다.

그렇다면 코드로는 어떻게 구현해 주어야 해당 파일이 끝날 때 멈출 수 있을까요?

    public static char[] cantor;//문자열을 입력할 배열

    public static void main(String[] args) throws IOException {
        //출력 시 속도를 줄이기 위한 StringBuilder
        StringBuilder stb = new StringBuilder();
        //EOF를 검사하기 위한 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String st;
        /*
        (st = br.readLine()) != null : EOF 확인
        !st.isEmpty() : Test시 엔터로 종료할 수 있도록
        */
        while((st = br.readLine()) != null && !st.isEmpty()){
            //입력 받은 값을 int 형식으로 변환
            int n = Integer.parseInt(st);
            
            //3의 배수만큼 배열을 만듬
            cantor = new char[(int) Math.pow(3, n)];
            
            //재귀 함수 실행
            cantorSet((int) Math.pow(3, n), 0, false);
            
            //만들어진 배열 stb에 저장
            for (char can : cantor) {
                stb.append(can);
            }
            stb.append("\n");
        }

        //출력
        System.out.println(stb);
    }

해당 방식을 EOF를 관리한다고 말하는데요 EOF는 End Of File입니다. 즉 파일의 끝을 확인한다는 말입니다.

파일의 끝을 확인하기 위해서는 BufferedReader라는 객체가 필요한데요. 해당 객체는 파일의 버퍼를 관리하는 객체로 입력 시 버퍼형식으로 받을 수 있도록 도와줍니다. 파일이나 byte을 관리할 때 BufferedReader과 InputStreamReader을 사용합니다. 자세히 설명하면 좋겠지만 지금은 백준 문제를 풀어야 하므로 "파일을 입력받을 때 사용하는 객체다" 정도로만 정리해 놓으시면 좋을 거 같습니다. 추후에 해당 객체에 대해 자세히 정리해 놓도록 하겠습니다.

여기서 저희는 파일로 테스트하는 게 아니고 tool안에서의 console창으로 입력을 합니다. 그렇기 때문에 파일 입력도 확인할 수 있고 cosole 입력도 확인하면서 에러가 나지 않도록 반복문을 구성해야 하는데 그 방법이 바로 위에 반복문 조건입니다. st!= null이 파일이 null이 될 때까지 돌려라(파일이 끝날때 까지) !st.Empty() 빈값이 입력될 때까지만 돌려라 라는 말입니다. 해당 조건이 동시에 만족할 때 종료하도록 하면 어떤 식으로 입력하든 올바르게 입력할 수 있습니다.

 

파일 입출력을 설명하느라 조금 다른 길로 갔는데 다시 돌아와서 어떻게 재귀를 해 구현할지 생각해 보겠습니다.

 

재귀로 구현하기 위해서는 가장 작은 단위를 생각하는 것이 중요합니다.

해당 문제에서 가장 작은 단위는 "-"가 3개일 때입니다.

그것보다 더 작은 단위는 -가 하나일 때입니다. 혹은 빈값이 들어갈 때이겠죠.

가장 작은 단위로 쪼개졌을 때 재귀 함수를 반환하면서 "-"혹은 빈값이 입력돼야 합니다. 이것이 기본적인 재귀의 구조입니다.

public static void cantorSet(int n, int x){
    if(n==1){
        cantor[x] = '-';
        return;
    }

    for(int i=0; i<3; i++){
        cantorSet(n/3,i);
    }
}

기본적으로 n을 계속해서 나눠서 1일 되었을 때(최소 단위일 때) 문자열을 입력하도록 해야 합니다. 그리고 해당 문자열을 어디에 입력할지 좌표 역시 넘겨주어야 하겠죠. 그래서 for문을 돌려서 해당 좌표를 넘겨주는 것입니다.

 

하지만 해당 코드는 문제가 있습니다. 최솟값만 생각했기 때문에 3 이상의 9,27 같은 수가 들어오면 3 이상의 문자열을 채우지 못한다는 것입니다.

 그러면 어떻게 해결해야 할까요?

위에 코드를 한번 분석해 보겠습니다.

만약 9가 n으로 들어왔다고 가정한다면 먼저 3으로 나눠진 값이 3번 돌면서 1~3을 채울 것입니다. 

그렇다면 3으로 나눠진 1~3을 채우는 3개의 재귀함수를 2번째일 때는 4~6을 세 번째일 때는 7~9를 채워주면 되지 않을까요?

그렇게 하기 위해서는 가장 문제인 반복문의 조건식을 변경해주어야 합니다. 해당 조건식이 3까지로 되어 있어서 3까지만 입력되는 것이니깐요. 해당 조건식은 x+n으로 변경해 줍니다. 이렇게 변경해 주면 해당 조건이 입력한 좌표에서 n만큼 더 돌 수 있음으로 9가 되든 21이 되든 최고 값까지 돌 수 있게 됩니다. 근데 이렇게 되면 n은 3인데 x가 8이어서 11까지 돌아 outOfIndex 에러가 날 수 있습니다.

그래서 변경해주어야 하는 것이 증감식입니다. 증감식을 1씩 증가하면 쓸데없이 두 번 입력을 하게 됩니다. 9일 때는 3씩 증가해야 하고 3일 때는 1씩 증가해야 하고 21일 때는 9씩 증가해야 해당 배열보다 값이 커졌을 때 반복문을 종료합니다.

그리고 마지막으로 초기값을 변경해 줍니다. 이것은 사실 0으로 해도 되지만 해당 값을 2번 입력할 필요가 없습니다.(나중에 빈값을 입력할 때 수정해야 합니다.) 초기값도 3으로 들어왔으면 0부터 9로 들어왔으면 첫 번째 3은 0부터 두 번째 3은 4부터 세 번째 3은 7부터 시작하면 됩니다.

public static void cantorSet(int n, int x){
    if(n==1){
        cantor[x] = '-';
        return;
    }

    int size = n/3;
    for(int i=x; i<x+n; i+=size){
        cantorSet(n/3,i);
    }
}

위에 코드까지 오셨다면 빈값을 채우는 것은 매우 쉽습니다. 

빈값이 들어가는 부분을 보시면 해당 배열의 2번째 값에서 빈값이 들어갑니다.

재귀에 들어갔을 때 2번째이면 해당 재귀를 빈값을 입력해 주고 재귀를 종료하면 됩니다.

 

    public static void cantorSet(int n, int x, boolean flag){

        //빈값을 입력
        if(flag == true){
            //여러건 일 때 빈 값 입력
            for(int i=0; i<n; i++){
                cantor[x+i] = ' ';
            }
            return;
        }

        //최소 값일 때 - 입력
        if(n==1){
            cantor[x] = '-';
            return;
        }

        int size = n/3;//3으로 나눠서 기준이 되는 값
        int count = 0;//빈값을 넣기 위한 count 변수
        //3으로 나눠 재귀
        for(int i=0; i<n; i+=size){
            count++;
            if(count == 2){
                cantorSet(n/3, x+i, true);
            }else{
                cantorSet(n/3, x+i, false);
            }

        }
    }