옛날에 python으로 풀었던 문제인데 java로 다시 풀어보게 되었다.
2021 포스팅 > 분할-정복-백준-2447번-별-찍기-10

사용 언어: java11

❓ Problem

문제 설명

문제

백준 2447번: 별찍기 - 10

🚩 Solution

1. 접근법

재귀는 일반화된 패턴을 분석하는 것이 중요하다.
별모양은 N이 얼마든 항상 9등분된 패턴 모양을 보인다.
따라서 위 그림처럼 패턴을 일반화할 수 있다.

완성된 별을 total 이라 하고, total 안에 반복되는 1/9 패턴을 piece라고 하겠다.
가장 먼저 할 일은 piece를 찾는 것이다.
만약, N=27이면 크기가 9인 piece를 찾아야 한다. 크기가 9인 piece를 찾으려면 크기가 3인 piece를 찾아야 한다.
문제 입력 조건에 따라 N=3 일 때 piece가 가장 작고, 이때 piece 찾기가 종료된다.

piece를 찾은 다음에는 piece를 별 모양에 맞게 붙이는 작업을 해야한다.
전체 별은 piece보다 큰데 인덱스 측면에서 piece를 어떻게 참조하면 될까? 이때는 % 연산자를 이용한다.
현재 인덱스 % piece의 길이로 구현하면 piece를 반복하여 참조할 수 있다.
별의 가운데 piece가 없는 곳은 piece 대신 공백을 채운다.

이제 코드로 살펴보자.

2. 코드

import java.util.*;

public class StarPrinting {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		String[][] answer = makeStar(N);
		for (String[] a: answer) {
			System.out.println(String.join("", a));
		}
	}

	private static String[][] makeStar(int N) {
		if(N == 3) {
			return new String[][] {{"*","*","*"}, {"*"," ","*"}, {"*","*","*"}};
		}

		String[][] piece = makeStar(N/3);
		String[][] total = new String[N][N];
        
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if((i>=N/3 && i<2*N/3) && (j>=N/3 && j<2*N/3)) {
					total[i][j] = " ";
					continue;
				}
				total[i][j] = piece[i%piece.length][j%piece.length];
			}
		}
        
		return total;
	}
}

함수 makeStar는 재귀적으로 N에 해당하는 패턴을 반환하는 기능을 수행한다.
기저 조건 N=3인 경우이거나 전체 total이 완성된 경우 return된다.

먼저 piece, 즉 N/3 크기의 패턴을 찾는다.
다음 반복문은 NxN 을 돌며 total을 만드는 과정이다.
가운데 범위는 조건문을 통해 공백으로 채워지게 하였다.
total은 piece의 반복이므로 인덱스%piece길이 로 인덱스를 참조하며 채워나간다.

3. 결과

성공

메모리: 128796 KB
시간: 712 ms