[JAVA]소용돌이 예쁘게 출력하기

문제

문제

 크기가 무한인 정사각형 모눈종이가 있다. 모눈종이의 각 정사각형은 행과 열의 쌍으로 표현할 수 있다.

 이 모눈종이 전체를 양의 정수의 소용돌이 모양으로 채울 것이다. 일단 숫자 1을 0행 0열에 쓴다. 그리고 나서 0행 1열에 숫자 2를 쓴다. 거기서 부터 소용돌이는 반시계 방향으로 시작된다. 다음 숫자는 다음과 같이 채우면 된다.

    -3 -2 -1  0  1  2  3
    --------------------
-3 |37 36 35 34 33 32 31
-2 |38 17 16 15 14 13 30
-1 |39 18  5  4  3 12 29
 0 |40 19  6  1  2 11 28
 1 |41 20  7  8  9 10 27
 2 |42 21 22 23 24 25 26
 3 |43 44 45 46 47 48 49

 이 문제는 위와 같이 채운 것을 예쁘게 출력하면 된다. r1, c1, r2, c2가 입력으로 주어진다. r1, c1은 가장 왼쪽 위 칸이고, r2, c2는 가장 오른쪽 아래 칸이다.

 예쁘게 출력한다는 것은 다음과 같이 출력하는 것이다.

1. 출력은 r1행부터 r2행까지 차례대로 출력한다.
2. 각 원소는 공백으로 구분한다.
3. 모든 행은 같은 길이를 가져야 한다.
4. 공백의 길이는 최소로 해야 한다.
5. 모든 숫자의 길이(앞에 붙는 공백을 포함)는 같아야 한다.
6. 만약 수의 길이가 가장 길이가 긴 수보다 작다면, 왼쪽에서부터 공백을 삽입해 길이를 맞춘다.

입력

첫째 줄에 네 정수 $r_1, c_1, r_2, c_2$가 주어진다.

출력

$r_2 - r_1 + 1$개의 줄에 소용돌이를 예쁘게 출력한다.

제한

• $-5 000 ≤ r1, c1, r2, c2 ≤ 5,000$
• $0 ≤ r2 - r1 ≤ 49$
• $0 ≤ c2 - c1 ≤ 4$

예제 입력 1

-3 -3 2 0

예제 출력 1

37 36 35 34
38 17 16 15
39 18  5  4
40 19  6  1
41 20  7  8
42 21 22 23

예제 입력 2

-2 2 0 3

예제 출력 2

13 30
12 29
11 28

예제 입력 3

-1 -2 -1 1

예제 출력 3

18  5  4  3

예제 입력 4

0 0 0 0

예제 출력 4

1

풀이

1. 처음의 풀이

• 입력값 중 절대값이 가장 큰 값을 기준으로 정사각형의 모눈종이를 만들어 값을 할당
• 그 모눈종이에서 입력값에 해당하는 사각형만큼만 출력을 진행

메모리 초과 발생. 출력에 필요한 부분만 메모리 할당을 하면 되는데, 정사각형의 모눈종이 전부를 할당하여 발생한 문제.

2. 두번째 풀이

• 반복문과 조건문을 통해 출력에 필요한 메모리에 값 할당.

시간 초과 발생. 많은 조건문으로 인해 연산 지연. 애초에 분석 및 설계를 잘못하여 발생한 문제.

3. 최종 풀이

• 소용돌이의 패턴을 보면 반시계 방향으로 진행된다.
• 처음에 (1)은 중앙에 입력, 그리고 (2) 오른쪽, (3) 위쪽, (4,5) 왼쪽, (6,7) 아래쪽, (8, 9, 10) 오른쪽, (11, 12, 13) 위쪽, ... 과 같이 진행된다.
• 입력되는 수의 개수는 위쪽 혹은 아래쪽으로 진행된 다음, 1개씩 증가하고, 방향은 반시계 방향이다.
• 전체 모눈종이를 다 할당하면 메모리 초과가 발생하므로, 좌표값이 입력값 범위 내에 있다면 할당하도록 한다.

public class _1022 {
    static int r1, r2, c1, c2, max = 0;
    static int map[][];
    //소용돌이가 반시계방향이므로 dx, dy의 값 순서는 아래와 같다.
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {1, 0, -1, 0};
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        r1 = Integer.parseInt(st.nextToken());
        c1 = Integer.parseInt(st.nextToken());
        r2 = Integer.parseInt(st.nextToken());
        c2 = Integer.parseInt(st.nextToken());
        map = new int[r2-r1+1][c2-c1+1];
        fill();
        print();
    }
    //배열에 값 할당하는 함수
    public static void fill(){
        int x = 0, y = 0, dir = 0;
        int num = 1, len = 1, cnt = 0;
        while(!end_check()){
            //범위 내에 오면 할당
            if(x >= r1 && x <= r2 && y >= c1 && y <= c2)
                map[x-r1][y-c1] = num;
            num++;
            cnt++;
            //좌표 변경
            x += dx[dir];
            y += dy[dir];

            if(cnt == len){
                cnt = 0;
                //방향이 위나 아래였으면 길이 증가
                if(dir == 1 || dir == 3)
                    len++;
                dir = (dir + 1) % 4;    //방향 전환
            }
        }
        max = num - 1;  //최댓값 저장
    }
    //출력 부분이 완성되었는지 여부
    public static boolean end_check(){
        return map[0][0] != 0 && map[r2-r1][0] != 0 && map[0][c2-c1] != 0 && map[r2-r1][c2-c1] != 0;
    }
    //출력 함수
    public static void print(){
        int max_len = (int)Math.log10(max); //최대자릿수 계산
        int len;
        for(int i = 0; i <= r2-r1; i++){
            for(int j = 0; j <= c2-c1; j++){
                len = max_len - (int)Math.log10(map[i][j]);
                //최대자릿수에 맞춰 공백 삽입
                for(int k = 0; k < len; k++)
                    sb.append(" ");
                sb.append(map[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}