Programmers | Level 2 | 행렬 테두리 회전하기
Programmers | Level 2 | 행렬 테두리 회전하기
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Matrix
Description
rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.
x1행y1열부터x2행y2열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.
다음은 6 x 6 크기 행렬의 예시입니다.
이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은 회전하지 않는 것을 주의하세요.
행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.
Constraints
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입니다. - 모든 회전은 순서대로 이루어집니다.
- 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.
Examples
| 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] |
Solutions
Code
import java.util.*;
class Solution {
public int[] solution(int rows, int columns, int[][] queries) {
// 행렬 초기화
int[][] grid = new int[rows][columns];
int number = 1;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
grid[i][j] = number++;
}
}
// 회전을 위한 방향 설정 (우, 하, 좌, 상)
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
List<Integer> minimums = new ArrayList<>();
for (int[] query : queries) {
int x1 = query[0] - 1;
int y1 = query[1] - 1;
int x2 = query[2] - 1;
int y2 = query[3] - 1;
// 테두리 회전을 위한 초기값 설정
int min = Integer.MAX_VALUE;
int px = x1, py = y1;
int prev = grid[px][py];
// 테두리 회전 (네 방향을 차례로 회전)
for (int d = 0; d < 4; d++) {
while (true) {
int nx = px + dx[d];
int ny = py + dy[d];
// 테두리를 벗어나면 다음 방향으로
if (nx < x1 || ny < y1 || nx > x2 || ny > y2) break;
// 숫자 회전
int next = grid[nx][ny];
grid[nx][ny] = prev;
prev = next;
// 최솟값 갱신
min = Math.min(min, next);
px = nx;
py = ny;
}
}
// 회전에서 가장 작은 값을 리스트에 추가
minimums.add(min);
}
return minimums.stream().mapToInt(i -> i).toArray();
}
}
Approach
이 문제는 주어진 행렬에서 특정 범위의 테두리를 시계 방향으로 회전시키고, 각 회전에서 이동된 숫자 중 가장 작은 값을 찾아내는 문제입니다. 이를 해결하기 위해서는 먼저 행렬을 초기화한 뒤, 주어진 범위의 테두리 부분을 따라 숫자들을 회전시키면서 값을 갱신합니다. 각 회전 과정에서 최솟값을 추적하여 결과를 저장하는 방식으로 진행됩니다. 이 과정은 매트릭스(Matrix) 유형에 속하며, 테두리 회전과 동시에 최소값을 효율적으로 계산하는 것이 핵심입니다.
1. 문제 분석
이 문제는 rows x columns 크기의 행렬에서 특정 범위의 테두리 부분을 반복적으로 시계 방향으로 회전시키고, 각 회전에서 이동한 숫자들 중 가장 작은 값을 반환하는 문제입니다.
행렬에서의 테두리 회전은 지정된 (x1, y1)부터 (x2, y2)까지의 좌표 범위를 포함하는 사각형의 테두리 부분을 한 칸씩 시계 방향으로 이동시키는 방식으로 이루어집니다. 이러한 회전 과정을 통해 행렬 내의 값들이 재배치되며, 각 회전마다 가장 작은 값을 찾아야 합니다.
문제를 해결하는 데 있어 중요한 부분은 회전할 범위의 테두리를 정확히 선택하고, 이를 시계 방향으로 올바르게 회전시키는 것입니다. 특히 좌표 이동을 처리할 때 각 회전 범위 내에서의 경계와 방향을 관리하는 것이 중요합니다. 각 회전에서 테두리의 값을 순차적으로 이동시키면서, 그 과정에서 최소값을 찾아내야 합니다.
결국, 행렬의 좌표 처리, 값의 순환 이동, 그리고 최소값 추출이라는 세 가지 주요 개념을 기반으로 해결해야 합니다. 이 과정에서 효율적인 좌표 계산과 반복적인 회전이 정확히 구현되어야 하며, 매 회전마다 테두리의 숫자 중 최소값을 추적하는 것이 관건입니다.
2. 접근 방식
이 문제를 해결하기 위해서는 먼저 행렬을 초기화하고, 주어진 각 회전에 따라 테두리 부분을 회전시키는 과정이 필요합니다. 구체적인 단계는 다음과 같습니다:
- 행렬 초기화: 주어진
rows와columns크기를 가진 행렬을 먼저 초기화합니다. 각 위치에는 1부터rows × columns까지의 값이 순차적으로 채워집니다. 이 초기화 과정은 이후 회전 작업을 위한 기본 준비 단계로, 각 숫자가 규칙적으로 배치되어 회전할 때 규칙적으로 이동될 수 있도록 보장합니다. - 테두리 회전:
queries에 주어진 각 회전 범위(x1, y1, x2, y2)에 대해, 해당 범위의 테두리를 시계 방향으로 회전시킵니다. 이 과정에서 각 테두리 요소를 새로운 위치로 이동시키면서, 그 순서가 올바르게 유지되도록 합니다. 이를 위해 테두리의 각 요소를 순차적으로 이동시키되, 미리 값을 저장해 두었다가 회전하는 방식으로 이동합니다. 회전할 때는 네 방향(위, 오른쪽, 아래, 왼쪽)을 순서대로 이동하면서 테두리 값을 처리해야 합니다. - 최솟값 찾기: 각 회전이 완료되면, 해당 테두리에서 이동된 값들 중 가장 작은 값을 찾아야 합니다. 회전 과정 중에 값을 비교하면서, 최솟값을 추적할 수 있도록 변수에 저장하고 업데이트합니다. 이를 통해 각 회전이 완료된 후, 가장 작은 값을 결과로 반환합니다.
이러한 단계를 반복적으로 수행하면서, 모든 회전에 대한 결과를 리스트에 기록하고 최종적으로 반환합니다.
3. 초기 행렬 구성
먼저, 주어진 rows와 columns 값을 기반으로 2차원 행렬을 초기화하는 작업을 진행합니다. 각 셀에는 1부터 순차적으로 숫자를 할당하여, 행렬을 완성합니다. 이 작업은 문제 해결을 위한 첫 단계로, 이후 주어지는 회전 쿼리를 처리할 준비를 하는 과정입니다.
행렬은 왼쪽 상단부터 오른쪽 하단까지, 숫자가 차례대로 채워지며, 이를 통해 이후 테두리 회전이 원활하게 이루어지도록 합니다. 각 숫자는 해당 위치의 고유 값으로, 회전이 일어날 때 테두리 값들이 이동하게 됩니다.
이렇게 완성된 행렬은 다음과 같은 구조를 가지며, 이후의 회전 작업에서 사용됩니다:
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 34 35 36
이처럼 초기 행렬을 구성함으로써, 이후 회전 쿼리에서 각 숫자가 움직이며 최솟값을 찾는 과정에 사용할 수 있게 됩니다.
4. 회전 방향 설정
테두리 회전을 수행하려면 이동할 방향을 설정해야 합니다. 이 문제에서는 각 테두리의 숫자를 시계 방향으로 회전시키는 것이 핵심입니다. 이를 위해 네 가지 방향, 즉 오른쪽, 아래, 왼쪽, 위로 이동하는 경로를 정의해야 합니다.
시계 방향으로 회전하는 흐름은 다음과 같습니다:
- 오른쪽으로 이동 (→): 현재 위치에서 같은 행을 유지하면서 열만 증가시킵니다.
- 아래쪽으로 이동 (↓): 가장 오른쪽 열에 도착한 후, 같은 열을 유지하면서 행만 증가시킵니다.
- 왼쪽으로 이동 (←): 가장 아래쪽 행에 도착하면, 같은 행을 유지하면서 열을 감소시킵니다.
- 위쪽으로 이동 (↑): 가장 왼쪽 열에 도착한 후, 같은 열을 유지하면서 행을 감소시킵니다.
이 네 가지 방향을 순서대로 따르며, 각 테두리를 따라 숫자를 한 칸씩 이동시킬 수 있습니다. 이를 구현하기 위해, 방향을 나타내는 델타 배열을 사용하여 이동 좌표를 쉽게 계산할 수 있습니다. 델타 배열은 이동 방향에 따라 현재 위치를 갱신하는데 필요한 좌표의 변화를 저장하는 배열입니다.
델타 배열은 다음과 같이 정의할 수 있습니다:
int[] dx = {0, 1, 0, -1}; // 행 방향으로 이동할 변화
int[] dy = {1, 0, -1, 0}; // 열 방향으로 이동할 변화
이 배열을 통해, 회전 중에 각 방향으로 이동할 때마다 dx와 dy를 활용하여 현재 위치를 갱신할 수 있습니다. 예를 들어, 오른쪽으로 이동할 때는 dx[0]과 dy[0]을 사용하여 열을 증가시키며, 아래쪽으로 이동할 때는 dx[1]과 dy[1]을 사용하여 행을 증가시킵니다.
5. 쿼리 범위 설정 및 회전 준비
테두리 회전을 수행하기 위해서는 주어진 쿼리에서 시작 좌표 (x1, y1)와 끝 좌표 (x2, y2)를 기준으로 회전 범위를 설정해야 합니다. 이 범위는 행렬에서 회전할 테두리의 영역을 나타냅니다. 각 쿼리는 직사각형의 테두리를 시계 방향으로 회전시키며, 범위 내에서 가장 작은 값을 추출하는 것이 목표입니다.
쿼리에서 제공되는 좌표는 1부터 시작하는 값이므로, 배열 인덱스에 맞추기 위해 0부터 시작하는 좌표로 변환해야 합니다. 즉, 각 좌표 값에서 1을 빼서 0 기반의 인덱스와 맞게 변환하는 과정이 필요합니다. 이렇게 변환된 좌표는 회전할 범위 내의 시작점과 끝점을 결정하는 데 사용됩니다.
int x1 = query[0] - 1; // 시작 행
int y1 = query[1] - 1; // 시작 열
int x2 = query[2] - 1; // 끝 행
int y2 = query[3] - 1; // 끝 열
회전을 준비하기 위해, 먼저 회전 범위의 시작점에 있는 숫자를 저장해둡니다. 이 숫자는 회전 과정 중 다른 위치로 이동할 값으로, 회전이 완료될 때까지 임시로 보관됩니다. 이와 동시에, 회전하는 동안 테두리의 숫자 중 가장 작은 값을 추적하기 위해 최소값을 저장할 변수를 초기화해야 합니다.
int min = Integer.MAX_VALUE; // 회전 범위 내의 최소값을 추적
int px = x1; // 현재 회전 위치를 쿼리의 시작점으로 설정
int py = y1;
int prev = grid[px][py]; // 회전 시작점에 있는 값을 임시로 저장
이렇게 회전을 준비하는 과정을 통해, 지정된 범위 내에서 숫자를 시계 방향으로 이동시킬 수 있는 준비가 완료됩니다.
6. 행렬 테두리 회전 및 최소값 추적
이제 준비한 좌표 설정과 방향 정보를 활용하여, 쿼리로 지정된 범위 내에서 테두리의 숫자를 시계 방향으로 회전시키면서 숫자 이동 및 최소값을 추적합니다. 회전은 상하좌우 네 가지 방향으로 진행되며, 각 방향으로 숫자를 한 칸씩 이동시키고, 이전에 있던 숫자는 임시로 저장한 후 다음 위치로 옮깁니다.
회전 과정의 첫 번째 단계는 쿼리로 주어진 테두리의 시작점부터 시작하여, 각 방향으로 숫자를 이동시키는 것입니다. 첫 번째 숫자를 임시로 저장하고, 각 방향으로 이동할 때마다 숫자를 한 칸씩 옮기며, 그 과정에서 가장 작은 값을 추적합니다.
숫자를 이동할 때, dx와 dy로 정의된 배열을 이용해 현재 좌표를 갱신하며, 테두리의 경계를 벗어나지 않도록 주의해야 합니다. 이동하는 동안, 현재 위치에 있는 숫자를 저장해 다음 위치로 옮기고, 그 과정에서 만나는 숫자 중 최소값을 계속 갱신해 나갑니다.
for (int d = 0; d < 4; d++) { // 시계 방향으로 4방향 이동
while (true) {
int nx = px + dx[d]; // 다음 이동할 행 계산
int ny = py + dy[d]; // 다음 이동할 열 계산
// 회전 범위를 벗어나면 이동 종료
if (nx < x1 || ny < y1 || nx > x2 || ny > y2) break;
// 현재 위치의 숫자를 다음 위치로 이동
int next = grid[nx][ny];
grid[nx][ny] = prev;
prev = next; // 이전 값을 갱신
// 이동 중 최소값 추적
min = Math.min(min, next);
// 현재 위치를 갱신
px = nx;
py = ny;
}
}
회전 중에 숫자를 이동하는 과정은 다음과 같은 순서로 진행됩니다:
- 오른쪽으로 이동: 테두리의 시작점에서 오른쪽으로 이동하며 숫자를 옮깁니다.
- 아래쪽으로 이동: 오른쪽 끝에 도달하면 아래로 이동하여 숫자를 옮깁니다.
- 왼쪽으로 이동: 아래쪽 끝에서 왼쪽으로 이동하며 숫자를 옮깁니다.
- 위쪽으로 이동: 왼쪽 끝에서 위로 이동하며 처음 위치로 돌아옵니다.
이 과정을 통해 테두리 내 모든 숫자들이 한 칸씩 시계 방향으로 회전됩니다. 회전이 완료되면, 해당 쿼리에서 추적된 최소값을 별도의 배열에 저장하여, 이후 결과로 반환할 수 있도록 합니다.
7. 최종 결과 배열 반환
모든 쿼리에 대해 테두리 회전과 최소값 추적이 완료되면, 각 쿼리에서 얻은 최소값을 배열 형태로 반환하는 단계입니다. 각 쿼리의 최소값을 편리하게 저장하기 위해 리스트를 사용했으며, 최종적으로 이 리스트를 배열로 변환해 반환해야합니다.
return minimums.stream()
.mapToInt(Integer::valueOf) // 리스트의 각 값을 정수형으로 변환
.toArray(); // 최종적으로 배열로 변환하여 반환
Complexity
- ⏳ TC: O(n)
- 💾 SC: O(n)
각 쿼리는 지정된 범위의 테두리를 시계방향으로 회전시키며, 회전 범위의 테두리 크기는 행과 열의 합에 비례합니다. 이 과정은 쿼리의 수 만큼 반복되므로, 최악의 경우 시간 복잡도는 O(n)으로 표현할 수 있습니다. 공간 복잡도는 행렬 전체를 저장하는 데 필요한 공간과, 각 쿼리의 최소값을 추적하기 위한 추가 공간을 사용하므로, O(n)입니다.
- Algorithm
- Matrix