[백준 1022] 소용돌이 예쁘게 출력하기 - JAVA

BOJ Link

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

 

 

 

풀이 과정

배열 돌리기류? 달팽이류? 단순 구현문제다.

어떤 좌표에 쓰인 수를 찾는 방법은 다음과 같이 구현했다.

 

ㅎㅎ;

초록색 좌표의 수를 찾으려 할때, 빨간색 영역을 미리 구해놓고, 파란색 좌표부터 반시계 방향으로 탐색하며 구해준다.

 

 

빨간색 영역의 크기는 다음과 같다.

int max = Math.max(Math.abs(r), Math.abs(c)) - 1;
int areaSize = (1 + max * 2) * (1 + max * 2);

 

파란색 좌표에는 무조건 빨간색 영역의 사이즈 +1인 수가 위치하며, c좌표 또한 +1 해준다.

int nr = max;
int nc = max + 1;
int num = areaSize + 1;

이후 델타 탐색을 사용하여, 반시계 방향으로 돌며 초록색 좌표의 수를 구해준다.

 

해당 과정을 (r2-r1+1) * (c2-c1+1)번 수행하여 배열에 저장하며, 가장 큰 수의 자릿수 또한 같이 구해준다.

마지막으로, 자릿수만큼 수의 앞에 공백을 추가하여 StrugBuilder에 저장한 후 출력한다.

 

시간 복잡도가 충분할 것 같아 이렇게 구현했는데, 아마 다양한 풀이가 존재할 것 같다.

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r1 = Integer.parseInt(st.nextToken());
        int c1 = Integer.parseInt(st.nextToken());
        int r2 = Integer.parseInt(st.nextToken());
        int c2 = Integer.parseInt(st.nextToken());
        int maxLen = 0;
        int rLen = Math.abs(r2 - r1) + 1;
        int cLen = Math.abs(c2 - c1) + 1;
        String[][] ans = new String[rLen][cLen];

        for (int i = 0; i < rLen; i++) {
            for (int j = 0; j < cLen; j++) {
                String num = String.valueOf(getNum(r1 + i, c1 + j));
                ans[i][j] = num;
                maxLen = Math.max(num.length(), maxLen);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < rLen; i++) {
            for (int j = 0; j < cLen; j++) {
                String s = ans[i][j];
                while (s.length() < maxLen) s = " " + s;
                sb.append(s+" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

    public static int getNum(int r, int c) {

        if (r == 0 && c == 0) return 1;

        int max = Math.max(Math.abs(r), Math.abs(c)) - 1;
        int areaSize = (1 + max * 2) * (1 + max * 2);

        int nr = max;
        int nc = max + 1;
        int num = areaSize + 1;

        int up = -(max + 1);
        int down = max + 1;
        int right = max + 1;
        int left = -(max + 1);

        while (nr > up) {
            if (nr == r && nc == c) break;
            nr--;
            num++;
        }

        while (nc > left) {
            if (nr == r && nc == c) break;
            nc--;
            num++;
        }

        while (nr < down) {
            if (nr == r && nc == c) break;
            nr++;
            num++;
        }

        while (nc < right) {
            if (nr == r && nc == c) break;
            nc++;
            num++;

        }

        return num;
    }
}