[BOJ][Recursion] 10994번 별 찍기-19

문제

www.acmicpc.net/problem/10994

10994번: 별 찍기 - 19

풀이

1) 초기 코드 (메모리 : 34892KB, 시간 : 1148ms)

import java.io.*;
import java.util.*;

public class Main {
	static char[][] star;
	static void print_stars(int row, int col, int N) {
		if(N==0)
			return;
		for(int i=row;i<(4*N-3)+row;i++) {
			if(i==row || i==4*N-4+row) {
				for(int j=col;j<4*N-3+col;j++)
    				star[i][j] = '*';
			}
			else {
				for(int j=row;j<4*N-3+row;j++) {
					if(j==col || j==4*N-4+col)
						star[i][j] = '*';
					else
						star[i][j] = ' ';
			}
			}
		}
		print_stars(row+2,col+2,N-1);
	}
	public static void main(String[] args) throws IOException {
        //선언 및 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	StringBuilder sb = new StringBuilder();
    	int N = Integer.parseInt(br.readLine());
    	star = new char[500][500];
    	//계산
    	print_stars(0,0,N);
    	for(int i=0;i<4*N-3;i++) {
    		for(int j=0;j<4*N-3;j++) {
    			System.out.print(star[i][j]);
    		}
    		System.out.println();
    	}
	}
} 

맨 위와 맨 아래의 별 갯수와 N과의 관계를 생각해봤고, 등차수열 점화식을 활용하여 별의 갯수 = 4*N -3을 도출했다.

이를 활용하여 배열에 별과 빈칸을 저장하여 답을 구했지만, 메모리와 시간이 많이 사용됐다. 더 효율적인 방법이 필요할 것으로 생각된다.

 

 

2) 메모리, 시간 절약 코드 (메모리 : 17084KB, 시간 : 180ms)

import java.io.*;
import java.util.*;

public class Main {
	static boolean[][] star;
	static void print_stars(int row, int col, int N) {
		if(N==0)
			return;
		int size = 4*N-3;
		int lastRow = row+size-1;
		int lastCol = col+size-1;
		for(int i=0;i<size;i++) {
			//맨 위, 맨 아래 별 찍기
			star[row][col+i] = true;
			star[lastRow][col+i] = true;
			//양 쪽 기둥 별 찍기
			star[row+i][col] = true;
			star[row+i][lastCol] = true;
		}
		print_stars(row+2,col+2,N-1);
	}
	public static void main(String[] args) throws IOException {
        //선언 및 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	StringBuilder sb = new StringBuilder();
    	int N = Integer.parseInt(br.readLine());
    	int size = 4*N -3;
    	//계산
    	star = new boolean[size][size];
    	print_stars(0,0,N);
    	
    	for(int i=0;i<size;i++) {
    		for(int j=0;j<size;j++) {
    			sb.append(star[i][j]?"*":" ");
    		}
    		sb.append("\n");
    	}
    	System.out.println(sb);
	}
} 

메모리 절약은 int 형 배열에서 boolean 형 배열로 바꿔서 절약된 것 같고, 실행 시간은 별 값을 저장할 때 2중포문에서 1중 포문으로 줄여서 획기적으로 줄어든 것으로 생각된다. 아직 많이 부족한 것 같다...ㅠㅠ