lango

찍먹? 부먹?
난 부먹 개발자.

3 minute read




문제 풀이

*로 이루어진 사각형의 패턴이 무엇인지 파악해보자.
N이 3이라면 가운데 한칸이 공백인 사각형을 나타냄을 알 수 있다.

1
2
3
4

N=3
***
* *
***


그러면 N이 3보다 큰 거듭제곱일 경우는 어떨까?
N이 9일 경우와 27일 경우에 별이 출력되는 패턴을 살펴보자. (보기 편하도록 * 사이에 공백을 추가한 사진을 첨부하였다.)

[N=9일 때]

[N=27일 때]

잘 보면 N이 9일 때와 27일 때 모두 N이 3일 때의 블록을 3X3의 크기로 출력됨을 알 수 있다.
즉 N/3 만큼 반복하여 각 블록을 채우고 있음을 알 수 있다.

  • N = 27일 경우는 9X9 크기의 별 사각형을 3X3 크기의 블록으로 출력한다. -> 9번 출력
  • N = 9일 경우는 3X3 크기의 별 사각형을 3X3 크기의 블록으로 출력한다. -> 3번 출력
  • N = 3일 경우는 3X3 크기의 별 사각형을 한 번 출력한다. -> 1번 출력

이를 통해 재귀함수 호출횟수는 N/3번이라는 것을 유추할 수 있다.


아이디어 도출

재귀함수를 이용한 아이디어를 생각해보았다.

  1. 모든 원소에 공백값이 저장된 2차원 배열을 활용한다.
    1.1 3X3 크기로 블록을 나누어 별을 출력한다고 생각하면 결국 가운데 칸인 (1,1) 좌표만 공백이 되면 된다.
    1.2 결국 (1,1) 좌표가 아닌 경우는 *을 저장하면 된다.
    1.3 모든 원소에 공백값을 저장하고 재귀함수를 통해 공백값이 아닌 위치에만 *을 저장한다.
    1.4 재귀함수의 종료 조건은 (N/3)만큼 재귀함수가 호출되면서 결국 N이 1이 되는 순간에 2차원 배열에 *을 저장한다.
  2. N/3만큼 1번 과정을 수행하는 재귀함수를 호출한다.
  3. *과 공백이 저장된 2치원 배열을 출력한다.


재귀함수 함수 작성

위 아이디어를 통해 생각해낸 재귀함수의 코드를 작성해보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public static void star(String[][] arr, int X, int Y, int N) {
    if(N == 1) {
        arr[X][Y] = "*";
        return;
    }
    else {
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                if(!(i==1 && j==1)) {
                    star(arr, X+i*(N/3), Y+j*(N/3), (N/3));
                }
            }
        }
    }
}

재귀함수 star는 매개변수로 2차원 배열과 x,y 좌표값, N을 받아 실행한다.
N이 1이 될 때까지 가운데 칸, 즉 (1,1) 좌표값이 아닐 경우에만 *을 저장해야 하기에 2중 for문 내에 ‘!(i==1 && j==1)’라는 조건을 부여했다.
그렇게 N/3만큼 재귀함수를 호출해가며 N이 1이 되는 순간에 *을 저장하면 된다.


이제 나머지 코드를 작성해보자.

1
2

int N = Integer.parseInt(br.readLine());        
String[][] arr = new String[N][N];

N을 입력받고 N*N 크기를 가진 2차원 배열 arr를 선언하자.

1
2
3
4
5

for(int i=0; i<N; i++) {
    for(int j=0; j<N; j++) {
        arr[i][j] = " ";
    }
}

그리고 아이디어대로 arr의 모든 자리를 공백값으로 채우고 star함수로 공백값이 아닌 자리에 *을 저장하기로 하였으니, 모든 원소를 공백값으로 채우자.

1
2
3
4
5
6
7
8

star(arr, 0, 0, N);

for(String[] arrs : arr) {
    for(String s : arrs) {
        bw.write(s+"");
    }
    bw.write("\n");
}

공백값으로 채워진 2차원 배열 arr를 star의 인자로 넘겨 함수를 실행하자. (X, Y 즉 인덱스 좌표는 0부터 시작해야 하니 0,0으로 넘겨준다.)
마지막으로 star 함수 실행 후 arr에 저장된 값을 출력하면 된다. 이 때, 각 행마다 개행을 넣어 출력해야 한다.



작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());        
        String[][] arr = new String[N][N];        

        // 1. 먼저 arr를 공백으로 채운다.
        // 2. star 함수에서 공백이 아닌 자리에 *을 채운다.

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                arr[i][j] = " ";
            }
        }

        star(arr, 0, 0, N);

        for(String[] arrs : arr) {
            for(String s : arrs) {
                bw.write(s+"");
            }
            bw.write("\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }   
    
    public static void star(String[][] arr, int X, int Y, int N) {
        if(N == 1) {
            arr[X][Y] = "*";
            return;
        }
        else {
            for(int i=0; i<3; i++) {
                for(int j=0; j<3; j++) {
                    if(!(i==1 && j==1)) {
                        star(arr, X+i*(N/3), Y+j*(N/3), (N/3));
                    }
                }
            }
        }
    }
}

회고

  • 매커니즘 자체는 단순했지만, 2차원 배열을 활용해 재귀함수를 구현하는 것까지 생각해내는게 어려웠던 문제였다.
  • 재귀함수를 호출해가며 재귀에서 가장 작은 단위의 연산을 실행한 후의 종료 조건을 잘 구성해야 함을 알 수 있었다.

You may also enjoy