출처: https://school.programmers.co.kr/learn/courses/30/lessons/77485
문제 설명
rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.
x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.
다음은 6 x 6 크기 행렬의 예시입니다.
grid_example.png
이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은 회전하지 않는 것을 주의하세요.
rotation_example.png
행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
rows는 2 이상 100 이하인 자연수입니다.
columns는 2 이상 100 이하인 자연수입니다.
처음에 행렬에는 가로 방향으로 숫자가 1부터 하나씩 증가하면서 적혀있습니다.
즉, 아무 회전도 하지 않았을 때, i 행 j 열에 있는 숫자는 ((i-1) x columns + j)입니다.
queries의 행의 개수(회전의 개수)는 1 이상 10,000 이하입니다.
queries의 각 행은 4개의 정수 [x1, y1, x2, y2]입니다.
x1 행 y1 열부터 x2 행 y2 열까지 영역의 테두리를 시계방향으로 회전한다는 뜻입니다.
1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columns입니다.
모든 회전은 순서대로 이루어집니다.
예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.
입출력 예시
rows columns queries result
6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]][8, 10, 25]
3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]][1, 1, 5, 3]
100 97 [[1,1,100,97]][1]
입출력 예 설명
입출력 예 #1
회전을 수행하는 과정을 그림으로 표현하면 다음과 같습니다.
example1.png
입출력 예 #2
회전을 수행하는 과정을 그림으로 표현하면 다음과 같습니다.
example2.png
입출력 예 #3
이 예시에서는 행렬의 테두리에 위치한 모든 칸들이 움직입니다. 따라서, 행렬의 테두리에 있는 수 중 가장 작은 숫자인 1이 바로 답이 됩니다.
내가 작성한 코드문
class Solution {
public int[] solution(int rows, int columns, int[][] queries) {
int[] answer = new int[queries.length];// 행의 사이즈 담기
// 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다.
// 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현
// 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return
int[][] arr = new int[rows][columns];// 행렬 배열
int min = Integer.MIN_VALUE;// 최솟값 담기
// rows, columns에 맞게 행렬만든다. 그리고 1부터 차례대로 행렬에 넣는다.
int num = 1;
for(int i = 0; i < rows; i++){
for(int j = 0; j < columns; j++){
arr[i][j] = num;
num++;
}
}
// 그다음에 쿼리 인덱스에 있는 범위대로 시계방향 회전 수행, 단 가운데 인덱스들은 안함
for(int i = 0; i < queries.length; i++){
min = Integer.MAX_VALUE; // 행한번 끝날때마다 초기화 해야함
for(int j = 0; j < queries[i].length; j=j+2){// 2씩움직이는게 맞음
// 2,2 / 5,4 이렇게 인덱스가 먹여짐
if(arr[queries[i][j]][queries[i][j+1]] < min){// 쿼리배열 인덱스를 arr에 넣는다.
min = arr[queries[i][j]][queries[i][j+1]];// 최솟값 min 배열에 저장
}
}
answer[i] = min;// 반복문 다 돌고 answer 배열에 최솟값 저장
}
return answer;
}
}이렇게 내 생각대로 코드문을 작성했는데..
현재 코드의 문제점
1. ✅ 회전을 하지 않고 있음
사실 회전을 하려면 어떻게 해야할지 부터가 막막했다.
이 코드는 단지 queries[i]에 있는 좌표들을 배열에 넣고 최솟값만 찾고 있다.
- ❌ IndexOutOfBounds 발생 가능
arr[queries[i][j]][queries[i][j+1]] 부분에서
입력되는 queries[i][j], queries[i][j+1] 값은 1-based인데 arr은 0-based 배열이다.
예를 들어, queries[i] = {2, 2, 5, 4}면
arr[2][2]을 참조하는 게 아니라, arr[1][1]을 참조해야 함
-1을 빼야 안전하게 동작
- ⚠️ 불필요한 반복 구조
for(int j = 0; j < queries[i].length; j = j + 2) 반복문은 필요 없다.
한 쿼리는 항상 [x1, y1, x2, y2] 형태이기 때문에 각 인덱스만 정확하게 분리하면 된다.
요구사항 반영된 코드문
class Solution {
public int[] solution(int rows, int columns, int[][] queries) {
int[] answer = new int[queries.length];
int[][] arr = new int[rows][columns];
int num = 1;
for(int i = 0; i < rows; i++) {
for(int j = 0; j < columns; j++) {
arr[i][j] = num++;
}
}
for(int i = 0; i < queries.length; i++) {
int x1 = queries[i][0] - 1;
int y1 = queries[i][1] - 1;
int x2 = queries[i][2] - 1;
int y2 = queries[i][3] - 1;
int temp = arr[x1][y1];
int min = temp;
// 왼쪽 세로
for(int r = x1; r < x2; r++) {
arr[r][y1] = arr[r + 1][y1];
min = Math.min(min, arr[r][y1]);
}
// 아래쪽 가로
for(int c = y1; c < y2; c++) {
arr[x2][c] = arr[x2][c + 1];
min = Math.min(min, arr[x2][c]);
}
// 오른쪽 세로
for(int r = x2; r > x1; r--) {
arr[r][y2] = arr[r - 1][y2];
min = Math.min(min, arr[r][y2]);
}
// 위쪽 가로
for(int c = y2; c > y1 + 1; c--) {
arr[x1][c] = arr[x1][c - 1];
min = Math.min(min, arr[x1][c]);
}
arr[x1][y1 + 1] = temp; // 마지막 한 칸 복원
answer[i] = min;
}
return answer;
}
}이중배열이면 반드시 이중반복문을 돌아야한다거나
int x1 = queries[i][0] - 1;
int y1 = queries[i][1] - 1;
int x2 = queries[i][2] - 1;
int y2 = queries[i][3] - 1;
와 같이 각 인덱스 별로 변수 만들어주는것도 생각 못함
① 왼쪽 세로 줄 ↓
for (int r = x1; r < x2; r++) {
arr[r][y1] = arr[r + 1][y1];
min = Math.min(min, arr[r][y1]);
}의미:
왼쪽 세로줄 값이 아래에서 위로 올라온 값으로 덮임 = 아래에서 위로 값이 이동
(→ 시계 방향에서 왼쪽 테두리 부분이 아래에서 위로 올라가야 하므로 맞음)실제로는 "아래에서 위로 복사한 것"
r은 x1부터 x2 - 1까지
arr[r][y1]은 현재 셀 → 아래에 있는 셀의 값을 복사받음 (arr[r+1][y1])
그리고 그 새 값이 회전한 값 중 최솟값인지 확인해서 min 갱신.
② 아래 가로 줄 →
for (int c = y1; c < y2; c++) {
arr[x2][c] = arr[x2][c + 1];
min = Math.min(min, arr[x2][c]);
}의미:
아래 가로줄 값이 오른쪽에서 왼쪽으로 이동됨 = 왼쪽으로 밀림
c는 y1부터 y2 - 1까지
현재 위치 arr[x2][c]는 오른쪽 셀 값을 받아와요 (arr[x2][c+1])
이후 min 갱신.
③ 오른쪽 세로 줄 ↑
for (int r = x2; r > x1; r--) {
arr[r][y2] = arr[r - 1][y2];
min = Math.min(min, arr[r][y2]);
}의미:
오른쪽 세로줄이 위에서 아래로 값이 내려온 것처럼 보이지만 사실은 아래에서 위로 복사됨 = 시계 방향 회전
r은 x2부터 x1+1까지 (역순)
현재 위치는 바로 위의 값을 받아옴 (arr[r - 1][y2])
최솟값 갱신
④ 위 가로 줄 ←
for (int c = y2; c > y1 + 1; c--) {
arr[x1][c] = arr[x1][c - 1];
min = Math.min(min, arr[x1][c]);
}의미:
위 가로줄 값이 왼쪽에서 오른쪽으로 이동됨 = 오른쪽으로 밀림
c는 y2부터 y1 + 2까지 (역순)
현재 위치는 바로 왼쪽 값을 받아옴 (arr[x1][c - 1])
최솟값 갱신
💡 마지막 남은 한 칸 처리
arr[x1][y1 + 1] = temp;
