[BOJ] 백준 2448 별찍기 - 11

출처: https://www.acmicpc.net/problem/2448

Approach

n이 주어졌을 때, 아래와 같은 별 모양을 형성하는 문제이다.

 

해당 문제는 다음과 같이 접근해보았다.

재귀적으로 아래의 각 삼각형 상단 좌표를 기준으로 해서 별모양을 형성

: (1) - (2) - (3) - [4]

 

※ Test Case 통과를 위해서는 아래사항을 주의.

1. null문자는 단 한개도 출력해서는 안된다.

    일부 환경 (예: 비주얼 스튜디오)에서는 널 문자가 마치 공백처럼 출력되어 눈에 보이지 않지만, 

    널 문자와 공백은 엄연히 다르며, 채점 프로그램은 단 한 개의 널 문자라도 발견되면 무조건 오답으로 처리

    공백은 무조건 공백 문자 ' ' 띄워쓰기를 이용해 출력.

2. 출력 예제를 드래그해보면 모든 줄은 같은 길이의 문자를 출력하고 있기에

    별 뒤에 공백밖에 남은 것이 없더라도 다 출력해줘야 합니다.

3. 출력의 크기가 어디까지 갈 수 있을지 잘 생각해보세요.

    이차원 배열을 이용한다면 세로는 최대 3*2^10이지만 세로는 가로의 2배이다. 

4. 별(*)을 출력할 때 속도제한에 신경써야 한다.

    가령, Java의 경우 System.out.print로는 속도의 한계가 있다. 

    → StringBuilder 이용.

 

▶ [문제] BOJ 별 찍기 시리즈

[문제] BOJ 별 찍기 시리즈

---

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
class Vertex{
    int x, y;
     
    public Vertex(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        // 가장 작은 N은 3이다.
        int N = Integer.parseInt(sc.next());
         
        // 인덱스를 1,1부터  시작한다.
        char[][] arr = new char[N + 1][N*2 + 1];
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=2*N; j++) {
                arr[i][j] = ' ';
            }
        }
        List<Vertex> list = new ArrayList<>();
        list.add(new Vertex(1, N));
         
        int target = N;
        while(true) {
            target = target / 2;
            if(target < 3) {
                break;
            }
             
            int listSize = list.size();
            for(int i=0; i<listSize; i++) {
                Vertex v = list.get(i);
                list.add(new Vertex(v.x + target, v.y - target));
                list.add(new Vertex(v.x + target, v.y + target));
            }
             
        }
 
        // 해당 정점들로 최소단위 삼각형태의 별모양을 형성한다.
        for(int i=0; i<list.size(); i++) {
            Vertex v = list.get(i);
             
            arr[v.x][v.y] = '*';
            arr[v.x+1][v.y-1] = '*'; arr[v.x+1][v.y+1] = '*';
            for(int j=v.y-2; j<=v.y+2; j++) {
                arr[v.x+2][j] = '*';
            }
        }
         
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=2*N; j++) {
                if(i==N && j==2*N) {
                    break;
                }
                sb.append(arr[i][j]);
            }
            if(i != N) {
                sb.append("\n");    
            }
             
        }
        System.out.print(sb.toString());
         
    }
}