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

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

2447번: 별 찍기 - 10

 

문제 설명

 

별 찍기 문제입니다. 숫자를 받고 해당 개수의 해당하는 가로세로의 별 찍기를 재귀로 구현합니다.

 

문제 풀이

 

저한테 이번 문제는 정말 어렵게 다가왔습니다.

정답률은 정말 높은데 저는 이 문제 때문에 며칠을 태웠는지 모르겠습니다.

문제도 거의 답보고 외운 수준이라 제가 풀었다고 말하기도 조금 민망합니다.

하지만 다음에 같은 문제를 만났을 때 어떤 식으로 접근해야 하는지 두 번째 만났을 때는 해결할 수 있도록 공부하고 적용하는 게 중요하겠죠. 제가 이해한 내용 대로 최대한 쉽게 정리해 보겠습니다.

 

먼저 생각해야 하는 것은 3일 때는 3*3의 별, 9일 때는 9*9의 별, 27일 때는 27*27의 별이 찍힌다는 것입니다.

이때 행열, 2차원 배열로 먼저 접근하는 것이 가장 쉽습니다. 줄 바꿈은 for문을 한번 더 돌리면 되고 해당 패턴에 따라 빈 공간만 채우면 별이 완성되게 됩니다.

다음과 같이 행열로 좌표처럼 생각하면 조금 접근하기가 수월해집니다.

사진 1

 

그리고 보니 조금 징그럽네요. 빨간색 상자가 계속해서 반복되는 패턴이라고 생각하시면 됩니다.

작은 패턴이 9번 중간이 빈 형태로 큰 패턴을 형성합니다.

 

이제 이것을 코드로 구현해야 하는데 쉽지 않았습니다.

먼저 위에 내용처럼 2차원 배열을 선언하고 해당 줄 수만큼 줄 바꿈을 하는 내용을 main 함수에 만들어 봅니다.

    static char[][] star_array;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        star_array = new char[n][n];

        StringBuilder stb = new StringBuilder();
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                stb.append(star_array[i][j]);
            }
            stb.append("\n");
        }

        System.out.println(stb);
    }

 지금은 2차원 배열에 아무것도 없으니 아무것도 출력되지 않을 것입니다.

StringBuilder를 사용한 것은 나중에 속도에서 걸리기 때문에 사용해 주었습니다.

n만큼 반복 후 줄 바꿈을 해주면 배열에는 편하게 해당 배열 번째에 빈칸과 별을 선택에서 넣어주기만 하면 됩니다.

 

그렇다면 이제부터 고민이 생깁니다.

어떻게 재귀를 사용해 해당 별을 만들 수 있을까..

먼저 3*3을 보겠습니다.

사진 2

5번째 별이 빈칸이 들어감을 알 수 있습니다.

9*9를 보겠습니다.

사진 3

역시 5번째 패턴일 때 빈값을 넣게 됩니다. 해당 패턴에 대한 이해 정도만 알고 넘어가도록 하겠습니다.

그렇다면 3*3부터 별을 어떻게 찍으면 좋을까요?

직관적으로 한번 만들어보겠습니다. 먼저 빈칸은 생각하지 않고 만들어보겠습니다.

private static void star(int x, int y, int n){
    if(n == 1){
        star_array[x][y] = '*';
        return;
    }

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

위에 코드처럼 짜게 되면 문제는 9를 넣었을 때 여전히 3*3 형식으로만 찍힌다는 것입니다.

왜일까요? 순서를 잘 생각해 보면 먼저 n/3을 해서 3이 size변수로 들어가게 될 것입니다.

그래서 3*3을 완성하고 해당 재귀를 빠져나올 것입니다.

이때 x:0, y:1 size는 3인 다음 재귀가 시작되는데

그렇게 되면 재귀 안에서는 i:0, y:1, size:1이 됨으로 배열[0][1]에 *이 찍히게 됩니다.

심지어 실질적으로 *을 찍는 반복문일 때 n은 3을 넘지 못함으로 3*3만 완성될 수밖에 없는 것입니다.

배열의 *이 적용되지 않아 null이 나온 모습

그러면 어떻게 하면 될까요? 우선 가장 큰 문제인 n을 수정해야 합니다. 3 이상을 넘지 못하니 3 이상을 넘을 수 있도록 수정해야 합니다. n=9인 경우에는 3*3 재귀를 빠져나온 후에 어떤 배열이 채워져야 하는지 알아야 합니다.

array [0~2][0~2] 까지는 모두 채워졌으므로 array [0~2][3~5]가 채워져야 합니다.

그러면 i, j이 n=3일 때는 1씩 늘어가고 9일 때는 3씩 늘어가는 것이 맞습니다.

그래야 3*3인 재귀가 끝나고 i:0, y:3 size:3인 재귀가 시작될 것이고 array [0~2][3~5]의 배열이 채워질 것입니다.(n도 3번 돌 수 있도록 size만큼 크기를 키워줘 y가 9까지 들어갈 수 있도록 합니다.)

사진 3번의 2번째 패턴을 그런 식으로 채워주는 것입니다.

private static void star(int x, int y, int n){
    if(n == 1){
        star_array[x][y] = '*';
        return;
    }

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

위에 코드처럼 n+y, y+=size로 반복문을 만들어 주어야 올바른 배열의 별을 채워줄 수 있습니다.

해당 아이디어를 생각하고 구현하는 게 쉽지는 않습니다.

여기까지 했다면 빈칸을 넣는 일은 매우 쉽습니다.

위에서 말했듯이 5번째 패턴의 반복일 때 빈칸을 넣어주면 됩니다.

 

아래에 코드는 문제가 있는 코드입니다. 무엇이 문제인지 아래서 설명하도록 하겠습니다.

private static void star(int x, int y, int n, boolean flag){
    if(flag == true){
        star_array[x][y] = ' ';
        return;
    }

    if(n == 1){
        star_array[x][y] = '*';
        return;
    }


    int size = n/3;
    int count = 0;
    for(int i=x; i<n+x; i+=size){
        for(int j=y; j<n+y; j+=size){
            count++;
            if(count == 5){
                star(i,j,size,true);
            }else{
                star(i,j,size,false);
            }

        }
    }
}

직관적으로 만들었습니다. count라는 변수를 만들어서 5번째에 들어갈 때 true라는 flag를 넘겨서 빈 값을 넣고 return 할 수 있도록 하였습니다. 그렇게 되면 3일 때는 array [1][1] 일 때 빈값이 들어갈 것이고 9일 때는 3*3의 모든 중간 패턴과  array [3][3] 일 때 빈값이 들어가고 바로 array [3][6]으로 시작하게 됩니다.

 

여기서 문제가 생깁니다. array [3][4~6] 빈값이 아닌 null값이 들어가게 됩니다.

위에 처럼 반복하지 않은 배열은 null값을 출력하게 됩니다.

그렇게 되면 true일 때 해당 패턴을 반복문으로 만들어 ' '으로 입력되도록 돌려주어야 합니다.

private static void star(int x, int y, int n, boolean flag){
    if(flag == true){
        for(int i=x; i<x+n; i++){
            for(int j=y; j<y+n; j++){
                star_array[i][j] = ' ';
            }
        }
        return;
    }

    if(n == 1){
        star_array[x][y] = '*';
        return;
    }


    int size = n/3;
    int count = 0;
    for(int i=x; i<n+x; i+=size){
        for(int j=y; j<n+y; j+=size){
            count++;
            if(count == 5){
                star(i,j,size,true);
            }else{
                star(i,j,size,false);
            }

        }
    }
}

위에 코드처럼 빈값을 설정해 주면 올바른 패턴을 만들 수 있습니다.

반복문을 너무 많이 돌려서 시간이 초과가 나는 것이 아닐까 걱정했는데(2중 for문이 3개나 되어서..) 재귀에서는 시간을 넉넉하게 주는 것 같습니다.

 

 

전체코드

import java.util.Scanner;

public class Number_2447 {
    static char[][] star_array;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        star_array = new char[n][n];

        star(0,0,n, false);

        StringBuilder stb = new StringBuilder();
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                stb.append(star_array[i][j]);
            }
            stb.append("\n");
        }

        System.out.println(stb);
    }

    private static void star(int x, int y, int n, boolean flag){
        if(flag == true){
            for(int i=x; i<x+n; i++){
                for(int j=y; j<y+n; j++){
                    star_array[i][j] = ' ';
                }
            }
            return;
        }

        if(n == 1){
            star_array[x][y] = '*';
            return;
        }


        int size = n/3;
        int count = 0;
        for(int i=x; i<n+x; i+=size){
            for(int j=y; j<n+y; j+=size){
                count++;
                if(count == 5){
                    star(i,j,size,true);
                }else{
                    star(i,j,size,false);
                }

            }
        }
    }
}

 

 

처음부터 바로 올바른 코드를 구현할 수는 없습니다. 일단 도전해서 짜본 후 무엇이 문제일까를 생각하고 하나하나 수정해 나가다 보면 올바른 길에 도착할 수 있을 것이라고 생각합니다.