백준 2447. 별찍기 - 10

문제 링크

난이도	정답률(_%)
Silver 1	50.255%

설계

• 패턴의 크기 N < 3^8
• 패턴의 제곱수 k < 8
• 크기 3의 모양대로 분할해서 출력해야한다는 것은 알 것 같았다.. 고민..
  • 크기 3을 출력해보자(가운데를 비운다)
    • 이중 포문 i, j를 3을 제한으로 돌려서, 가운데인 i = j = 1일 때만 출력하지 않는다.
  • 크기 9를 출력해보자
    • 크기 3인 패턴을 출력하는 함수를 이중 포문으로 3번 돌려서,
    • i = j = 1일 때만 출력하지 않도록 한다.
  • 크기 27은 크기 9를 3번 돌려서... 이런식으로 재귀를 만들어보자

시간 복잡도

• 패턴 제곱 수 k에 대해서 O(9^(k-1))
  • 크기 3짜리 패턴을 만드는데 for문 9번
  • 크기 9짜리 패턴을 만들려면 크기 3짜리를 9번
  • 크기 27짜리 패턴을 만들려면 크기 9짜리를 9번 (크기 3짜리를 81번)
  • ...

공간 복잡도

• 패턴을 저장하는 char형 이중 배열 N*N

고생한 점

• 배열을 한칸 빈 공백 문자열로 초기화를 안해서 고생..
  • IDE에선 한칸 빈 걸로 잘 나오는데 백준에선 그렇게 안되는듯 😥

풀이

• 이중포문 i, j < 3
  • i = j = 1 이면 아무것도 하지 않는다.
  • 그 외에는 크기를 3으로 나눠서 크기가 1이 될 때까지 재귀문을 돈다.
  • 크기가 1이 되면 * 패턴을 찍고 탈출한다.

결과

메모리	실행 시간
24060KB	192ms

코드

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

public class Main {
    private static int patternSize;
    private static char[][] patterns;

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

        patternSize = Integer.parseInt(br.readLine());
        patterns = new char[patternSize][patternSize];

        for (char[] patternRow : patterns) {
            Arrays.fill(patternRow, ' ');
        }

        makePattern(0, 0, patternSize);

        for (char[] patternRow : patterns) {
            bw.write(patternRow);
            bw.write("\n");
        }

        bw.flush();
        bw.close();
    }

    public static void makePattern(int row, int col, int size) {
        if (size == 1) {
            patterns[row][col] = '*';
            return;
        }

        int newSize = size / 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i == 1 && j == 1) {
                    continue;
                }

                makePattern(row + (i * newSize), col + (j * newSize), newSize);
            }
        }
    }
}