문제
재귀적으로 별을 출력하는 문제다. 크기 N (3의 제곱수)의 패턴은 크기 N/3 패턴 9개를 3×3으로 배치하되, 가운데 부분은 공백으로 채운다. 즉, N=3이면 8개의 별과 1개의 공백(가운데)으로 이루어진 3×3 패턴이 된다.
입력
- 첫째 줄: N (N은 3의 제곱수, 1 ≤ N ≤ 2187)
출력
N줄에 걸쳐 별 패턴 출력
예제
| 입력 | 출력 |
|---|---|
9 | (3×3 블록 9개, 가운데 블록이 공백인 9×9 패턴) |
풀이
분할 정복으로 전체 그리드를 N/3 크기의 9개 블록으로 나누고, 5번째(가운데) 블록만 공백으로 채운다. 재귀 호출은 크기가 1이 될 때까지 반복된다.
star(idx, jdx, n, blank)함수를 정의한다.blank가 true이면 해당 영역을 공백으로 채우고 반환한다.n == 1이면 별(*)을 찍고 반환한다.- n/3 크기의 9개 서브블록을 순서대로 재귀 호출한다. 5번째(count == 5)에는
blank = true로 호출한다. - 최종 출력 시 2차원 배열을 줄 단위로 출력한다.
핵심 아이디어: 전체 N×N 배열을 미리 선언하고 재귀로 값을 채운다. blank 플래그를 재귀 인자로 전달하여 가운데 영역 전체를 공백으로 처리한다. 9개 서브블록 중 정확히 5번째가 가운데다.
코드
package com.ssafy.an.day049;
import java.util.Arrays;
import java.util.Scanner;
public class Day38BOJ2447별찍기재귀 { // 2447 별 찍기 재귀
static char[][] star;
static int N;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
star = new char[N][N];
star(0, 0, N, false);
for (int i = 0; i < N; i++) {
System.out.println(Arrays.toString(star[i]).replaceAll("[\\[\\]]", "").replaceAll(", ", ""));
}
sc.close();
}
static void star(int idx, int jdx, int n, boolean b) {
if (b) {
for (int i = idx; i < idx + n; i++) {
for (int j = jdx; j < jdx + n; j++) {
star[i][j] = ' ';
}
}
return;
}
if (n == 1) {
star[idx][jdx] = '*';
return;
}
int size = n / 3;
int count = 0;
for (int i = idx; i < idx + n; i += size) {
for (int j = jdx; j < jdx + n; j += size) {
count++;
if (count == 5)
star(i, j, size, true);
else
star(i, j, size, false);
}
}
}
}복잡도
- 시간: O(N^2) — N×N 전체 셀을 한 번씩 방문
- 공간: O(N^2) — 결과 저장을 위한 2차원 배열