본문 바로가기
Algorithm/Baekjoon

[백준] 2447번 : 별 찍기 - 10 - Java

by unknownomad 2022. 4. 6.

https://www.acmicpc.net/problem/2447

 

2447번: 별 찍기 - 10

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이

www.acmicpc.net

주의점

  • Scanner + System.out.println(): 시간 초과됨
  • 출력 방법 : StringBuilder / BufferedWriter 활용하기

알고리즘

N = 3일 때 한 블럭의 모양

  • 블럭의 가운데는 공백

N = 31

N = 32 = 9

N = 33 = 27

N이 3의 제곱수일 때

 

정리

N = 27 일 때

  • 9개의 블록으로 구분
  • 공백 구간 만족 시 그 구간은 공백으로 채우기
  • 공백 구간 아닌 블럭은 재귀호출

N = 9 일 때

  • 9개의 블록으로 구분
  • 공백 구간 만족 시 그 구간은 공백으로 채우기
  • 공백 구간 아닌 블럭은 재귀호출

N = 3 일 때

  • 9개의 블록으로 구분
  • 공백 구간 만족 시 그 구간은 공백으로 채우기
  • 공백 구간 아닌 블럭은 재귀호출

N = 1 일 때

  • 더 이상 쪼갤 수 없기에 해당 구역의 배열을 공백 or 별(*)로 채우기

풀이

1.1. Scanner + StringBuilder

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: 별 출력 누적
        각 재귀 노드 별 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);
                }
            }
        }
    }
}

 

1.2. Scanner + BufferedWriter

import java.util.Scanner;
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 {
    
        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: 별 출력 누적
        각 재귀 노드 별 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);
                }
            }
        }
    }
}

 

2.1. BufferedReader + StringBuilder

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: 별 출력 누적
        각 재귀 노드 별 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);
                }
            }
        }
    }
}

 

2.2. BufferedReader + BufferedWriter

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: 별 출력 누적
        각 재귀 노드 별 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.1. BufferedReader + String.format() + 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: 별 출력 누적
        각 재귀 노드 별 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);
                }
            }
        }
    }
}

 

3.2. BufferedReader + String.format() + 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());
        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: 별 출력 누적
        각 재귀 노드 별 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);
                }
            }
        }
    }
}

성능

1. 입력

  • BufferedReader > Scanner

2. 출력

  • 출력 행이 많고 한 행씩 처리하는 프로세스 기준
  • BufferedWriter > StringBuilder

 

출처 : https://st-lab.tistory.com/95

'Algorithm > Baekjoon' 카테고리의 다른 글

[백준] 2798번 : 블랙잭 - Java  (0) 2022.04.12
[백준] 11729번 : 하노이 탑 이동 순서 - Java  (0) 2022.04.07
[백준] 10870번 : 피보나치 수 5 - Java  (0) 2022.04.05
[백준] 1002번 : 터렛 - Java  (0) 2022.04.04
[백준] 3053번 : 택시 기하학 - Java  (0) 2022.04.04

관련글

댓글

티스토리툴바