백준 2447번
https://www.acmicpc.net/problem/2447
문제
재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.
크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.
***
* *
***N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.
입력
첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.
출력
첫째 줄부터 N번째 줄까지 별을 출력한다.
예제 입력
27예제 출력
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
********* *********
* ** ** * * ** ** *
********* *********
*** *** *** ***
* * * * * * * *
*** *** *** ***
********* *********
* ** ** * * ** ** *
********* *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************생각하기
솔직히 이문제 개인적으로 너무 어려웠다.. 최근에 동적계획법을 공부하면서
재귀를 통한 분할 정복도 공부를 해야 한다고 생각해서 문제를 풀게 됬는데,
설계를 어떻게 해야할지 부터 감이 안잡혀서 1시간 정도를 고민하다가 다른 분의 풀이를 참고했다.
이 문제를 풀고 별을 출력할 때 StringBuilder와 BufferedWriter 2가지중 하나를 선택해서 출력해야 했다.
하지만 기존까지는 항상 StringBuilder만 사용해서 출력해놨었는데,
이번에 BufferedWriter를 처음 사용해봤는데,
StringBuilder보다 꽤 많이 결과과 좋아서 놀라웠다.
동작
int size = N / 3;
int count = 0;
for(int i=x; i<x + N; i+=size) {
for(int j=y; j<y + N; j+=size) {
count ++;
if(count == 5) {
makeStar(i, j, size, true);
}
else {
makeStar(i, j, size, false);
}
}
}위에서 배열생성과 초기화 등의 내용은 생략하고 "*" 을 배열에 넣는 것 부터 설명을 해보겠다.
먼저 처음 시작하면, 위 코드부터 실행이 될텐데
우리가 별을 찍는 과정은 작은 모양의 사각형부터 만들어야 한다는 점을 생각해야 한다.
N이 27일때, 9의 사각형이 먼저 완성되어야 하고, 9의 사각형이 완성되기 전에 3의 사각형이 먼저 완성되어야 한다.
그리고 3의 사각형을 만들기 위해서는 하나의 별을 출력해야 한다.
N -> 27 -> 9 -> 3 -> 1의 순서로 크기자체를 작은 모양의 사각형 부터 처리해야 한다.
그리고 if(count == 5) {의 조건은 N이 3일때 별은 5번째에서 공통적으로 공백이 찍히게 된다.
그래서 count의 변수를 반복이 한번 될 때 마다 증가시켜서 5번째에 위치할 때 공백을 처리할 수 있도록 만들었다.
크기인 N에 맞는 x와 y의 좌표값을 만들어서 그 크기만큼 순회하며 반복하도록 만드는 것이 목표인 셈이다.
// 공백칸일 경우
if(blank) {
for(int i=x; i<x + N; i++) {
for(int j=y; j<y + N; j++) {
arr[i][j] = ' ';
}
}
return;
}
if(N == 1) {
arr[x][y] = '*';
return;
}
이제 전체를 순환해서 재귀함수가 실행될 때,
N 즉 크기가 1일 때는 별을 배열에 넣는다.
또는 count == 5 조건에 걸려서 blank가 true일 때는
크기에 맞게 공백을 출력하게 된다.
코드
BufferedWriter 사용
import java.io.*; public class Main { static char arr[][]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int N = Integer.parseInt(br.readLine()); arr = new char[N][N]; makeStar(0, 0, N, false); // 출력 for(int i=0; i<N; i++) { bw.write(arr[i]); bw.write('\n'); } bw.flush(); bw.close(); } // End of main static void makeStar(int x, int y, int N, boolean blank) { // 공백칸일 경우 if(blank) { for(int i=x; i<x + N; i++) { for(int j=y; j<y + N; j++) { arr[i][j] = ' '; } } return; } if(N == 1) { arr[x][y] = '*'; return; } int size = N / 3; int count = 0; for(int i=x; i<x + N; i+=size) { for(int j=y; j<y + N; j+=size) { count ++; if(count == 5) { makeStar(i, j, size, true); } else { makeStar(i, j, size, false); } } } }// End of makeStar } // End of class
StringBuilder 사용
import java.io.*; public class Main { static char arr[][]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); //27은 3의 세제곱 arr = new char[N][N]; makeStar(0, 0, N, false); // arr 배열 출력. StringBuilder sb = new StringBuilder(); for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { sb.append(arr[i][j]); } sb.append('\n'); } System.out.println(sb); } // End of main static void makeStar(int x, int y, int N, boolean blank) { // 공백칸일 경우 if(blank) { for(int i=x; i<x + N; i++) { for(int j=y; j<y + N; j++) { arr[i][j] = ' '; } } return; } // 더이상 쪼갤 수 없는 블록일 때 // 27 -> 9 -> 3 -> 1로 와서 N이 1일때 if(N == 1) { arr[x][y] = '*'; return; } int size = N / 3; int count = 0; for(int i=x; i<x + N; i+=size) { for(int j=y; j<y + N; j+=size) { count ++; if(count == 5) { makeStar(i, j, size, true); } else { makeStar(i, j, size, false); } } } }// End of makeStar } // End of class
