백준 2447번 문제풀이 - 별찍기 - 10

백준 2447번 문제

 

 

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

2447번: 별 찍기 - 10

 

재귀로 같은 패턴의 별찍기를 하게 되는 문제이다. 처음에 어떤 패턴이 반복되는지는 이해가 같지만 어떻게 코딩으로 구현해야될지는 감이 잡히지 않아서 다른 사람의 풀이도 보면서 문제를 혼자 풀게되는데는 3일이 걸린 것 같다.

 

 

 

 

 

코딩

 

 

public class Star10 {
    static char[][] star;
    static void stamp(char[][] star, int x, int y, int N) {
        // 별을 찍게 됨
        if (N == 1) {
            star[x][y] = '*';
        }
        // 별을 찍게 되는 경우마다 호출
        if (N > 1) {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (!(i == 1 && j == 1)) {
                        stamp(star, x + i * (N / 3), y + j * (N / 3), N / 3);
                    }
                }
            }
        }
    }

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

        int n = Integer.parseInt(br.readLine());
        star = new char[n][n];

        for (int i = 0; i < n; i++) {   // 전체 배열을 공백으로 초기화
            for (int j = 0; j < n; j++) {
                star[i][j] = ' ';
            }
        }
        // 별찍는 메서드
        stamp(star, 0, 0, n);
        // 별 출력
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(star[i][j]);
            }
            sb.append('\n');
        }
        System.out.println(sb);
    }
}

 

별을 찍게 되는 경우의 for문을 살펴보면

배열의 행열에서 0부터 3의 배수로 증가하며 호출되는 것을 볼 수 있다.

i와 j가 1일 경우는 공백이기 때문에 그 외에 호출 되도록하여 *을 찍게 된다.

N = 3일 경우 

N / 3 = 1이 되면서 *이 찍히게 되는데

(0,0) -> (0, 1) -> (0, 2) -> (1, 0) -> (1, 1)찍히지 않음 -> (1, 2) -> (2, 0) -> (2, 1) -> (2, 2) 순으로 찍히게 된다.

N = 9일 경우

N / 3 = 3이 되면서 위와 같은 과정이 호출되며 반복된다.

 

 

 

 

 

결과

 

 

시간 초과가 나게된 것은 StringBuilder를 사용하지 않았을 때이고 StringBuilder를 출력할 때 사용하여 맞을 수 있었다.

 

 

 

 

 

느낀 점

 

재귀를 이해하려고 여러 문제를 접하고 있지만 설명을 하려고 글을 쓰다보면 부족한 부분이 많다는 것을 느낀다. 설명에 자신이 없고 다른 문제에 잘 적용하여 풀 수 있을지 의문이 들기 때문이다. 결국 많이 풀어보는 수 밖에 없는 것 같다.