[백준] 2447번 : 별 찍기 - 10 - JAVA [자바]
2447번: 별 찍기 - 10
재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 �
www.acmicpc.net
-
문제
- 알고리즘 [접근 방법]
필자가 이 문제를 푼 것은 좀 오래전이지만 근래 작성한 문제 중에 가장 설명하기 어려운 문제였다.
어떻게 설명해야하는지 고민을 좀 많이 했던지라..
또한 규칙은 쉽게 보이지만 이를 구현하자니 필자도 꽤 고민했던 문제이기도 했다.
(근데 정답률이 어떻게 50% 가까이 되는지 정말 신기하다.. 막상 질문하는 사람은 많은데..?)
여하튼 차근차근 한 번 풀어보도록 하자.
일단 문제의 규칙을 봐야 한다.
아마 이 그림을 보고 규칙은 대부분 다 찾아냈을 것이다.
일단 주어지는 수는 3의 거듭제곱 수이고
N=3 일 때의 모양은 다음과 같다.
이 모양이 연속적으로 채우면서 진행되는데 단, 한 block 의 '가운데' 는 채우지 않는다는 것이다.
무슨 말인가 하면
N = 31 일 때는 아래와 같고,
N = 32 = 9 일 때는 아래와 같고,
N = 33 = 27 일 때는 아래와 같다.
즉, N 이 3의 제곱수로 나올 때, 대략적인 그림으로 본다면 다음과 같다.
그러면 어떻게 이를 재귀를 써서 봐야 할까..?
규칙은 일단 한 block 에서 '가운데' 부분은 공백이라는 것이다.
우리는 2차원 배열과 행을 x, 열을 y 로 생각해보면 된다.
N = 3 일 때만 생각해보자
2차원 배열이 선언되었다는 가정하에 ( arr[][] )
인덱스는 0 부터이므로 N = 3 일 때의 공백은 arr[1][1] 이다.
이 의미는 즉 행부터 채울 때, (0, 0), (0, 1), (0, 2), (1, 0) 까지는 별을 출력하고
별 출력이 4 번 이루어지면 그다음 블럭은 반드시 공백이라는 것이다.
그리고 N = 9 일 때를 생각해보자.
N = 3 일 때의 모양이 한 블럭이 되어 똑같이 되풀이된다..
그러면 재귀로는 어떻게 풀어야 하냐가 문제다.
아이디어는 매우 매우 쉽다.
먼저 N = 27 일 때 우리는 9개의 블록으로 구분할 수 있다.
위 수식에서 보았듯이 공백인 구간을 만족한다면 그 구간은 공백으로 채우고
공백 구간이 아닌 블럭은 재귀호출을 하면 된다.
그러면 N = 9 일 때로 넘어갈 것이다.
또 앞선 함수와 같이 9개의 블록으로 나눈 뒤,
공백 구간은 공백 문자로 채우고 공백이 아닌 구간을 다시 재귀 호출을 하는 것이다.
그렇게 된다면 N = 3 일 때로 갈 것이고,
위와 같은 과정을 반복하다 보면 결국 N = 1 일 때가 온다.
여기서는 더 못 쪼개기 때문에 해당 구역의 배열을 공백 또는 별(*) 로 채우면 되는 것이다.
말로 하면 잘 이해가 안 될 테니 그림으로 보자면 다음과 같은 과정을 거친다고 보면 된다.
즉, 각 단계에서 9칸으로 구분 한 뒤, x, y 좌표에 따라서 공백 또는 재귀 호출을 반복해주어 더 이상 나눌 칸이 없을 때까지 반복하는 것이다.
간단한 코드로 보면 아래와 같다.
char[][] arr = new arr[N][N];
// blank 가 true 라면 공백칸임을 의미
void star(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;
}
/*
N=27 일 경우 한 블록의 사이즈는 9이고,
N=9 일 경우 한 블록의 사이즈는 3이듯
해당 블록의 한 칸을 담을 변수를 의미 size
count 는 별 출력 누적 합을 의미하는 변수다.
*/
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) { // 공백 칸일 경우
star(i, j, size, true);
}
else {
star(i, j, size, false);
}
}
}
}
이렇게 가장 작을 단위까지 재귀를 호출하면서 가장 작을 단위가 될 때, 하나씩 배열을 채워나가는 방법이다.
이렇게 문제를 분할하여 푸는 방식은 분할 정복 알고리즘의 토대가 되기도 한다.
- 3가지 방법을 이용하여 풀이한다.
알고리즘은 위에서 설명한 그대로 풀 것이다.
다만 입력만 달리하여 Scanner 와 BufferedReader 을 통한 방법으로 보여줄 것이다.
그리고 중요한 점은 Scanner 로 풀 때는 기존 출력 방법으로는 시간 초과가 난다.
System.out.print 를 할 때, 일단 N = 27 일 때만 하더라도 729번, 개행까지 포함하면 756번이나 출력해야 한다.
그렇기 때문에 StringBuilder 로 묶던, BufferedWriter 을 쓰건 둘 중 하나를 선택해야 한다.
필자는 일단 여러분들이 가장 이해하기 쉬운 StringBuilder 로 풀겠다.
그리고 위 재귀를 배열 대신 String 클래스와 StringBuilder 을 통해 색다른 방법도 보여주려 한다.
- 풀이
- 방법 1
import java.util.Scanner;
public class Main {
static char[][] arr;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
arr = new char[N][N];
star(0, 0, N, false);
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.print(sb);
}
static void star(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;
}
/*
N=27 일 경우 한 블록의 사이즈는 9이고,
N=9 일 경우 한 블록의 사이즈는 3이듯
해당 블록의 한 칸을 담을 변수를 의미 size
count는 별 출력 누적을 의미
*/
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) { // 공백 칸일 경우
star(i, j, size, true);
} else {
star(i, j, size, false);
}
}
}
}
}
가장 기본적인 방법이라 할 수 있겠다.
알고리즘은 위에서 설명한 것 그대로 적용했다.
만약 BufferedWriter 을 적용하려면 아래 더보기를 눌러 확인하시길 바란다.
[방법 1 - 1]
import java.util.Scanner;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
// BufferedWriter 버전
public class Main {
static char[][] arr;
public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Scanner in = new Scanner(System.in);
int N = in.nextInt();
arr = new char[N][N];
star(0, 0, N, false);
/*
BufferedWriter 의 write 메소드는 배열도 순서대로 출력해주기 때문에
2차원 배열의 경우 한 행씩 write 해주면
자체에서 해당 행의 열들을 순서대로 담아준다.
*/
for (int i = 0; i < N; i++) {
bw.write(arr[i]);
bw.write("\n");
}
bw.flush();
bw.close();
}
static void star(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;
}
/*
N=27 일 경우 한 블록의 사이즈는 9이고,
N=9 일 경우 한 블록의 사이즈는 3이듯
해당 블록의 한 칸을 담을 변수를 의미 size
count는 별 출력 누적을 의미
*/
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) { // 공백 칸일 경우
star(i, j, size, true);
} else {
star(i, j, size, false);
}
}
}
}
}
아마 수행 시간은 StringBuilder 보다 훨씬 빠를 것이다.
그리고 BufferedWriter 는 flush() 와 close() 를 해줘야 정상적으로 출력을 할 수 있다.
- 방법 2
Scanner 대신 BufferedReader 을 사용하는 방법이다.
위와 같은 알고리즘이고 입력 방법만 달리했다.
혹여나 BufferedWriter 로 쓴 것을 원하는 분들도 있을 수 있어 밑에 더 보기로 남겨두겠다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
static char[][] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
arr = new char[N][N];
star(0, 0, N, false);
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.print(sb);
}
static void star(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;
}
/*
N=27 일 경우 한 블록의 사이즈는 9이고,
N=9 일 경우 한 블록의 사이즈는 3이듯
해당 블록의 한 칸을 담을 변수를 의미 size
count는 별 출력 누적을 의미
*/
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) { // 공백 칸일 경우
star(i, j, size, true);
} else {
star(i, j, size, false);
}
}
}
}
}
아래 더보기는 BufferedWriter 을 이용한 출력방식이다.
[방법 2-1]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
public class Main {
static char[][] arr;
public static void main(String[] args) throws IOException {
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];
star(0, 0, N, false);
for (int i = 0; i < N; i++) {
bw.write(arr[i]);
bw.write("\n");
}
bw.flush();
bw.close();
}
static void star(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;
}
/*
N=27 일 경우 한 블록의 사이즈는 9이고,
N=9 일 경우 한 블록의 사이즈는 3이듯
해당 블록의 한 칸을 담을 변수를 의미 size
count는 별 출력 누적을 의미
*/
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) { // 공백 칸일 경우
star(i, j, size, true);
} else {
star(i, j, size, false);
}
}
}
}
}
- 방법 3
이 방법은 사실 약간은 얍삽한(?) 방법으로 String 클래스의 format() 과 StringBuilder 을 이용하여 푼 방법이다.
굳이 배열이 아닌 StringBuilder 을 배열처럼 이용하면 어떨까라는 생각에서 접근해보았다.
물론 StringBuilder 객체에 계속 접근해야 해서 생각보다 성능이 좋지 않을 것 같단 생각이 들긴 한다...
(재미 삼아.. 이런 방법도 있구나 하고 봐주시면 감사합니다)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
static StringBuilder[] sb;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
sb = new StringBuilder[N];
String s = String.format("%" + N + "s" , ' ');
for(int i = 0; i < N; i++) {
sb[i] = new StringBuilder(s);
}
star(0, 0, N);
for (int i = 0; i < N; i++) {
System.out.println(sb[i]);
}
}
static void star(int x, int y, int N) {
// 더이상 쪼갤 수 없는 블록일 때
if (N == 1) {
sb[x].setCharAt(y, '*');
return;
}
/*
N=27 일 경우 한 블록의 사이즈는 9이고,
N=9 일 경우 한 블록의 사이즈는 3이듯
해당 블록의 한 칸을 담을 변수를 의미 size
count는 별 출력 누적을 의미
*/
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) {
star(i, j, size);
}
}
}
}
}
간단히 이 방법을 설명하자면 미리 String.format 을 이용하여 공백 문자를 N 길이만큼 만들고, 그렇게 만들어진 문자열을 미리 StringBuilder 에 저장해놓고 시작하는 것이다.
그리고 재귀 함수에서 공백 부분이 아닌 부분만 공백을 * 로 치환한 뒤, 출력하는 방법이다.
물론 * 로 채우고 공백만 치환하는 반대의 방법도 가능하다.
[방법 3-1]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
static StringBuilder[] sb;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String s = String.format("%" + N + "s", ' ').replace(' ', '*');
sb = new StringBuilder[N];
for(int i = 0; i < N; i++) {
sb[i] = new StringBuilder(s);
}
star(0, 0, N, false);
for (int i = 0; i < N; i++) {
System.out.println(sb[i]);
}
}
static void star(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++) {
sb[i].setCharAt(j, ' ');
}
}
return;
}
// 더이상 쪼갤 수 없는 블록일 때
if (N == 1) {
return;
}
/*
N=27 일 경우 한 블록의 사이즈는 9이고,
N=9 일 경우 한 블록의 사이즈는 3이듯
해당 블록의 한 칸을 담을 변수를 의미 size
count는 별 출력 누적을 의미
*/
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) { // 공백 칸일 경우
star(i, j, size, true);
}
else {
star(i, j, size, false);
}
}
}
}
}
이렇게 다양한 방법이 있다~ 라는 정도만 알아두셔도 된다.
- 성능
위에서부터 순서대로
채점 번호 : 19821734 - 방법 3-1 : StringBuilder 문자열 치환 방법 2
채점 번호 : 19821728 - 방법 3 : StringBuilder 문자열 치환방법 1
채점 번호 : 19821720 - 방법 2-1 : BufferedReader + BufferedWriter
채점 번호 : 19821718 - 방법 2 : BufferedReader + StringBuilder
채점 번호 : 19821712 - 방법 1-1 : Scanner + BufferedWriter
채점 번호 : 19821708 - 방법 1 : Scanner + StringBuilder
입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.
그리고 이번 문제는 출력 행이 많고, 한 행씩 처리하다 보니 StringBuilder 보다는 BufferedWriter 가 성능이 훨씬 좋은 것을 볼 수 있다.
- 정리
아마 근래 포스팅한 글 중 가장 힘들었지 않았나... 싶다.
재귀 자체는 아이디어만 잘 떠오르면 구성하기는 쉽지만, 막상 설명하려면 여간 쉬운 게 아니라는 걸 다시 한번 느낀다.
많은 분들이 최대한 이해할 수 있도록 쉽게 풀어써봤지만,, 혹시 이해가 안 된다면 댓글 남겨주시면 설명이 부족한 부분을 추가해서 설명해주겠다.
그리고 생각보다 StringBuilder 을 활용해서 한 것도 성능이 꽤 좋게 나와서 당황했다..
'JAVA - 백준 [BAEK JOON] > 재귀' 카테고리의 다른 글
| [백준] 11729번 : 하노이 탑 이동 순서 - JAVA [자바] (25) | 2020.05.16 |
|---|---|
| [백준] 10870번 : 피보나치 수 5 - JAVA [자바] (16) | 2020.05.13 |
| [백준] 10872번 : 팩토리얼 - JAVA [자바] (2) | 2020.05.11 |