백준 알고리즘 2447번 별 찍기 문제풀이 - 자바(JAVA)

⚡️문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

⚡️입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

⚡️출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

📌 예제 입력 1 복사

27

📌 예제 출력 1 복사

***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

---

⚡️결과

별 하나하나 출력하면 시간이 초과되었습니다.

 

그래서 StringBuilder와 BufferedWriter를 사용해 출력하였는데

StringBuilder는 속도면에서 우위를 가지고 있고

BufferedWriter는 메모리면에서 우위를 가지고 있었습니다.

 

---

⚡️코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

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

        int size = Integer.parseInt(br.readLine());
        arr = new String[size][size];
        
        star(0, 0, size);

        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                // null 상태로 있는 빈공간을 채워주기
                bw.write(arr[i][j] != null ? arr[i][j] : " ");
            }
            bw.write("\n");
        }
        bw.flush();
    }

    public static void star(int x, int y, int size) {
        // 최소 단위(1)로 분할했으면 별 저장
        if(size == 1){
            arr[x][y] = "*";
            return;
        }

        // size가 1이 될 때까지 3X3 크기로 계속해서 분할
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                // 가운데 빈공간이면 건너뛰기 (null 상태로 유지하기)
                if(!(i==1 && j==1)) 
                    // x, y 값을 계속 유지하며 재귀 호출
                    star(x + i*size/3, y + j*size/3, size/3);
            }
        }
    }
}

---

⚡️문제풀이

이 풀이는 일종의 분할 정복법으로 정복할 수 있는 최소 단위까지 분할해 주어야 합니다.

 

한 변의 길이가 N이라면 N = 3^k의 입력이 들어옵니다.

 

// size가 1이 될 때까지 3X3 크기로 계속해서 분할
for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
        // 가운데 빈공간이면 건너뛰기 (null 상태로 유지하기)
        if(!(i==1 && j==1)) 
            // x, y 값을 계속 유지하며 재귀 호출
            star(x + i*size/3, y + j*size/3, size/3);
    }
}

별을 찍기위한 최소의 형태가 아래와 같이 가운데가 비어있는 3X3 형태이므로

3X3 형태로 계속해서 가로 세로 3분할해주고 변의 길이(size)를 N/3 만큼 재귀 호출해줍니다.

 

또한 별을 찍기 위해 x, y좌표를 다음과 같이 계속해서 더해줍니다. 

x + i*size/3, y + j*size/3

 

for(int i=0;i<size;i++){
    for(int j=0;j<size;j++){
        // null 상태로 있는 빈공간을 채워주기
        bw.write(arr[i][j] != null ? arr[i][j] : " ");
    }
    bw.write("\n");
}
bw.flush();

가운데 빈칸은 빈칸에 해당하는 좌표가 반복문에 들어올 시 건너뛰게 해 Null 값을 유지시키도록 한 뒤

출력할 때 삼항연산자로 빈칸을 입력해주었습니다.