문제
https://programmers.co.kr/learn/courses/30/lessons/77485
rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다.
행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.
생각하기
어려운 문제는 아니었지만, 공간감각이 부족한 나한테는 복잡한 문제였던 것 같다.
머리로 암산해서 풀기는 무리였고, 손으로 직접써서 풀어가니 쉽게 풀 수 있었다.
동작
int count = 1;
for(int i=0; i<rows; i++) {
for(int j=0; j<columns; j++) {
map[i][j] = count;
count ++;
}
}우선 전역변수map에 1부터 값이 증가하며 담기는 배열을 생성해주었다.
for(int i=0; i<len; i++) {
int x1 = queries[i][0];
int y1 = queries[i][1];
int x2 = queries[i][2];
int y2 = queries[i][3];
rotation(x1-1, y1-1, x2-1, y2-1);
list.add(min);
}그리고 query로 들어오는 배열값을 매개변수로 rotation 메소드를 실행시킨다.
static void rotation(int x1, int y1, int x2, int y2) {
min = Integer.MAX_VALUE / 16;
copy();
// 2 2 5 4 -> 1 1 4 3
// (1,1) -> (4,3) 회전
// 8부터 28까지를 회전 (중앙 빼고 테두리만)
// 상단 회전
// temp1,1 -> map1,2
// temp1,2 -> map1,3
for(int i=y1; i<y2; i++) {
min = Math.min(temp[x1][i], min);
map[x1][i+1] = temp[x1][i];
}
// 우측 회전
// temp 1,3 -> map 2,3
// temp 2,3 -> map 3,3
// temp 3,3 -> map 4,3
for(int i=x1; i<x2; i++) {
min = Math.min(temp[i][y2], min);
map[i+1][y2] = temp[i][y2];
}
// 하단 회전
// temp 4,3 -> map 4,2
// temp 4,2 -> map 4,1
for(int i=y2; i>y1; i--) {
min = Math.min(temp[x2][i], min);
map[x2][i-1] = temp[x2][i];
}
// 좌측 회전
// temp 2,1 -> map 1,1
// temp 3,1 -> map 2,1
// temp 4,1 -> map 3,1
for(int i=x2; i>x1; i--) {
min = Math.min(temp[i][y1], min);
map[i-1][y1] = temp[i][y1];
}
} // End of rotaionrotation함수를 통해서 배열 map을 회전시킨다.
여기서 회전시키기 전에 기존의 값을 가지고 있는 배열이 필요하므로 copy 메소드를 실행해서 map과 똑같은 크기와 값을 가지는 temp배열을 만들어준다.
이 temp의 값을 회전하는 좌표에 map을 넣어주면 map을 회전시킬 수 있다.
그리고 회전하는 동안 min에 최소값을 찾으며 갱신할 수 있도록 Math.min메소드를 넣어주면 답을 찾을 수 있게된다.
코드
import java.util.*; class Solution { static int map[][]; static int temp[][]; static int rows, columns; static int min; // 문제 : x1행 y1열 x2행 y2열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전 // 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return public int[] solution(int rows, int columns, int[][] queries) { this.rows = rows; this.columns = columns; map = new int[rows][columns]; temp = new int[rows][columns]; int len = queries.length; List<Integer> list = new ArrayList<>(); int count = 1; for(int i=0; i<rows; i++) { for(int j=0; j<columns; j++) { map[i][j] = count; count ++; } } for(int i=0; i<len; i++) { int x1 = queries[i][0]; int y1 = queries[i][1]; int x2 = queries[i][2]; int y2 = queries[i][3]; rotation(x1-1, y1-1, x2-1, y2-1); list.add(min); } int size = list.size(); int[] answer = new int[size]; for(int i=0; i<size; i++) { answer[i] = list.get(i); } return answer; } // End of solution // map배열 temp로 카피하는 메소드 static void copy() { for(int i=0; i<rows; i++) { for(int j=0; j<columns; j++) { temp[i][j] = map[i][j]; } } } // End of copy static void rotation(int x1, int y1, int x2, int y2) { min = Integer.MAX_VALUE / 16; copy(); // 2 2 5 4 -> 1 1 4 3 // (1,1) -> (4,3) 회전 // 8부터 28까지를 회전 (중앙 빼고 테두리만) // 상단 회전 // temp1,1 -> map1,2 // temp1,2 -> map1,3 for(int i=y1; i<y2; i++) { min = Math.min(temp[x1][i], min); map[x1][i+1] = temp[x1][i]; } // 우측 회전 // temp 1,3 -> map 2,3 // temp 2,3 -> map 3,3 // temp 3,3 -> map 4,3 for(int i=x1; i<x2; i++) { min = Math.min(temp[i][y2], min); map[i+1][y2] = temp[i][y2]; } // 하단 회전 // temp 4,3 -> map 4,2 // temp 4,2 -> map 4,1 for(int i=y2; i>y1; i--) { min = Math.min(temp[x2][i], min); map[x2][i-1] = temp[x2][i]; } // 좌측 회전 // temp 2,1 -> map 1,1 // temp 3,1 -> map 2,1 // temp 4,1 -> map 3,1 for(int i=x2; i>x1; i--) { min = Math.min(temp[i][y1], min); map[i-1][y1] = temp[i][y1]; } } // End of rotaion } // End of Solution class
