[알고리즘] 백준 > #2447. 별찍기 10

작심2일

오늘도 알고리즘 문제를 풀었다~

여러 타입의 알고리즘 문제를 풀고 좀 익숙해진 다음에 릿코드에서 랜덤으로 문제를 뽑아보기로했당. 오늘의 알고리즘은 분할정복(divide & conquer)

문제링크

백준 #2447. 별찍기 10

풀이방법

큰~ 문제를 작은 문제로 쪼개는게 분할정복의 핵심이다.

일단 계속 삼등분한다. 크기가 마침대 1이 되면 그때 별을 해당 자리에 넣어준다. 근데 가운데가 비워져있어야하기 때문에 삼등분 하는 과정에서 가운데를 따로 식별하고, 가운데라면 암것두 하지않는다~_~

간단하쥬?

코드

import java.util.Scanner;

public class printStars {
    static String[][] starMap;
    static int n;

    static int[] divY = {0, 0, 0, 1, 1, 1, 2, 2, 2};
    static int[] divX = {0, 1, 2, 0, 1, 2, 0, 1, 2};

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

        starMap = new String[n][n];

        for (int y = 0; y < n; y++) {
            for (int x = 0; x < n; x++) starMap[y][x] = " ";
        }

        fillStarMap(n, 0, 0);

        StringBuilder output = new StringBuilder();
        for (int y = 0; y < n; y++) {
            for (int x = 0; x < n; x++) {
                output.append(starMap[y][x]);
            }
            output.append("\n");
        }

        System.out.print(output.toString());
        // 이렇게 스트링빌더로 한 번에 출력하지 않고 매번 출력하면 시간초과가 난다!
    }

    private static void fillStarMap(int size, int y, int x) {
        if (size == 1) {
            starMap[y][x] = "*";
        } else {
            int tempSize = size / 3;
            for (int i = 0; i < 9; i++) {
                int tempY = y + (divY[i] * tempSize);
                int tempX = x + (divX[i] * tempSize);

                if (!(divY[i] == 1 && divY[i] == divX[i])) fillStarMap(tempSize, tempY, tempX);
            }
        }
    }
}

• 주석에도 나와있는데 Java로 알고리즘 푸는게 첨이라 처음엔 모든 배열 원소를 따로따로 출력해 시간초과가 났다 ㅋㅋ 스트링빌더로 한번에 출력해 해결~(스트링빌더를 사용하는 이유는 [Java] String, StringBuffer, StringBuilder 이 게시물을 확인하세용)