[백준] 1022 소용돌이 이쁘게 출력하기(JAVA)
문제 분석
- 크기가 무한대인 정사각형 모눈종이에 소용돌이 모양의 반시계 방향으로 양의 정수를 채움
- 제시된 범위에 맞는 소용돌이 이쁘게 출력하기
의사 결정
- 처음에는 이중 배열을 구현하여 값을 채워넣고, 제시한 범위만 잘라서 출력하도록 했지만 메모리 초과로 실패했습니다.
- -5 000 ≤ r1, c1, r2, c2 ≤ 5,000 으로 좌표 값이 크게 설정되면 이중 배열이 너무 커지기 때문에 메모리 초과가 발생한 것으로 추측됩니다.
- 각 좌표의 값을 소용돌이 규칙에 따라 계산하고, 제시된 이중 배열 범위에 추가하여 출력하는 방식을 사용했습니다.
코드 구현
1. 각 좌표 (R1, C1, R2, C2) 입력
공백을 기준으로 split으로 잘라 각 자표를 변수에 저장했습니다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int R1 = Integer.parseInt(input[0]);
int C1 = Integer.parseInt(input[1]);
int R2 = Integer.parseInt(input[2]);
int C2 = Integer.parseInt(input[3]);
2. 출력 범위 만큼 배열 크기 설정
(R1,C1) 부터 (R2, C2) 까지의 크기를 구하여 이중 배열로 설정했습니다.
int rows = R2-R1+1;
int cols = C2-C1+1;
int[][] arr = new int[rows][cols];
3. 소용돌이 값 계산 및 배열 저장
각 좌표에 해당하는 소용돌이 값을 getSpiralValue 함수에서 계산하고, 배열에 저장했습니다.
출력할 때 자릿수를 맞추기 위해 가장 큰 수를 찾을 수 있도록 했습니다.
int maxNumber = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int value = getSpiralValue(R1 + i, C1 + j);
arr[i][j] = value;
maxNumber = Math.max(maxNumber, value);
}
}
getSpiralValue 함수
- 레이어 계산
인자로 받은 좌표가 몇 층에 위치해있는지 계산하기 위해 좌표의 절대값 중 가장 큰 수로 설정했습니다.
예를 들어서 좌표가 0,0 이면 0층이고, 1,0 이거나 0,1 이면 1층 입니다.
- 해당 층의 최대 값 계산
각 레이어에서 숫자는 (3,3) 좌표 기준으로 시계 방향으로 감소합니다.
레이어의 시작 값과 끝 값을 알기 위해 레이어에 속하는 가장 큰 값(오른쪽 하단)을 계산해주었습니다.
- 각 층에 값을 계산
레이어에 속하는 가장 큰 값을 사용해서 각 좌표에 해당하는 숫자를 계산했습니다.
계산하는 방식으로 사용하는 소용돌이는 왼쪽 -> 위쪽 -> 오른쪽 -> 아래쪽으로 숫자가 감소되어집니다.
각 방향으로 이동할 때마다 숫자가 차례로 배열에 채워지고, 각 방향에서의 숫자는 이전 방향에서 시작된 숫자에 빼서 계산했습니다.
소용돌이 배열에서 각 변의 길이는 2 * 레이어 입니다. 각 변마다 값을 차례로 감소시키기 위해서 각 변의 크기만큼 빼주었습니다. 방향이 전환될 때마다 2 * 레이어가 누적되기 때문에 2, 4, 6 을 곱해주었습니다.
변의 위치에 따라 정확한 위치를 반영하기 위해 레이어에 x, y를 더하거나 빼주었습니다.
static int getSpiralValue(int x, int y) {
int layer = Math.max(Math.abs(x), Math.abs(y)); // 몇 번째 소용돌이 층인지 계산
int maxLayerValue = (2*layer+1) * (2*layer+1);
int result;
if(x == layer) // (하단) 우 -> 좌 이동
result = maxLayerValue - (layer - y);
else if(y == -layer) // (하단) 좌 -> (상단) 좌 이동
result = maxLayerValue - (2 * layer) - (layer - x);
else if(x == -layer) // (상단) 좌 -> (상단) 우 이동
result = maxLayerValue - (4 * layer) - (layer + y);
else // (상단) 우 -> (하단) 우 이동
result = maxLayerValue - (6 * layer) - (layer + x);
return result;
}
4. 자리수 맞추고, 결과 출력
가장 큰 수의 자릿수를 계산하여 모든 숫자가 그 자리수만큼 정렬되도록 했습니다.
String.format()를 사용해 자릿수를 맞추고, 출력했습니다.
int maxDigits = String.valueOf(maxNumber).length();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
sb.append(String.format("%" + maxDigits + "d ", arr[i][j]));
}
sb.append("\n");
}
System.out.print(sb);
전체 코드
package Beakjoon.gold;
import java.util.*;
import java.io.*;
public class bj1022 {
public static void main(String[] args) throws Exception {
StringBuilder sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int R1 = Integer.parseInt(input[0]);
int C1 = Integer.parseInt(input[1]);
int R2 = Integer.parseInt(input[2]);
int C2 = Integer.parseInt(input[3]);
// 출력 범위 만큼 배열 크기 설정
int rows = R2-R1+1; // 7
int cols = C2-C1+1; // 4
int[][] arr = new int[rows][cols];
// 출력할 때 최대 자릿수를 맞춰서 공간을 비워줘야하기 때문에 가장 큰 숫자를 찾기
int maxNumber = 0;
for(int i=0 ; i<rows; i++) {
for(int j=0 ; j<cols ; j++) {
int value = getSpiralValue(R1+i, C1+j); // 좌표의 소용돌이 값을 계산
arr[i][j] = value;
maxNumber = Math.max(maxNumber, value);
}
}
int maxDigits = String.valueOf(maxNumber).length();
for(int i=0 ; i<rows ; i++) {
for(int j=0 ; j<cols ; j++) {
sb.append(String.format("%"+maxDigits+"d ", arr[i][j]));
}
sb.append("\n");
}
System.out.print(sb);
}
static int getSpiralValue(int x, int y) {
int layer = Math.max(Math.abs(x), Math.abs(y)); // 몇 번째 소용돌이 층인지 계산
int maxLayerValue = (2*layer+1) * (2*layer+1);
int result;
if(x == layer) // (하단) 좌 -> 우 이동
result = maxLayerValue - (layer - y);
else if(y == -layer) // (하단) 좌 -> (상단) 좌 이동
result = maxLayerValue - (2 * layer) - (layer - x);
else if(x == -layer) // (상단) 좌 -> (상단) 우 이동
result = maxLayerValue - (4 * layer) - (layer + y);
else // (상단) 우 -> (하단) 우 이동
result = maxLayerValue - (6 * layer) - (layer + x);
return result;
}
}