[코딩테스트 연습] 행렬 테두리 회전하기
[문제링크]
rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.
- x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.
행렬의 세로 길이(행 개수) 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] |
-전체코드
import java.util.*;
class Solution {
public int[] solution(int rows, int columns, int[][] queries) {
int[] answer = new int[queries.length];
int[][] matrix = new int[rows][columns];
int count = 1;
// 행렬 초기화
for(int x = 0 ; x < rows ; x++) {
for(int y = 0 ; y < columns ; y++) {
matrix[x][y] = count++;
}
}
// answer에 사용될 count로 초기화
count = 0;
for(int[] i : queries) {
// 회전좌표를 받아옴
int x1 = i[0]-1;
int y1 = i[1]-1;
int x2 = i[2]-1;
int y2 = i[3]-1;
// 회전하기 전 첫 번째 값을 임시로 저장
int temp = matrix[x1][y1];
// 회전하는 숫자들 중 가장 작은 값을 찾기 위한 TreeSet
TreeSet<Integer> set = new TreeSet<>();
// (x1, y1) ~ (x2, y1) 까지 회전 (회전하는 사각형의 왼쪽)
for(int x = x1 ; x < x2 ; x++) {
matrix[x][y1] = matrix[x+1][y1];
set.add(matrix[x][y1]);
}
// (x2, y1) ~ (x2, y2) 까지 회전 (회전하는 사각형의 아래쪽)
for(int y = y1 ; y < y2 ; y++) {
matrix[x2][y] = matrix[x2][y+1];
set.add(matrix[x2][y]);
}
// (x2, y2) ~ (x1, y2) 까지 회전 (회전하는 사각형의 오른쪽)
for(int x = x2 ; x > x1 ; x--) {
matrix[x][y2] = matrix[x-1][y2];
set.add(matrix[x][y2]);
}
// (x1, y2) ~ (x1, y1+1) 까지 회전 (회전하는 사각형의 위쪽)
// (x1, y1+1)은 첫 번째 값을 받아오므로 temp를 저장
// 회전으로 인해 첫 번째 값 위치에 이미 회전한 숫자가 배치되었기때문
for(int y = y2 ; y > y1+1 ; y--) {
matrix[x1][y] = matrix[x1][y-1];
set.add(matrix[x1][y]);
}
matrix[x1][y1+1] = temp;
set.add(matrix[x1][y1+1]);
answer[count++] = set.first();
}
return answer;
}
}
- 막혔던 점 & 해결방법
행렬의 회전은 각 숫자가 한 칸씩 자리를 이동하는 것입니다.
문제의 그림을 인용하여 설명하면 행렬의 왼쪽, 아래, 오른쪽, 위 테두리를 각각 하나의 배열로 보아 문제를 해결하였습니다. 각 테두리 배열에서 다음 칸의 값을 현재 칸의 값으로 가져오며, 제일 마지막 칸의 값은 temp라는 임시 저장변수에서 가져오게 됩니다. 각 테두리를 순회하며 해당 칸의 값을 TreeSet에 저장하게 되고, 저장된 TreeSet의 첫 번째 값이 곧 최솟값이 됩니다.
- 느낀점
처음부터 모든 회전을 구현하기보다 각 테두리로 쪼개어 회전을 구현하니 수월하게 풀 수 있었습니다.
Author And Source
이 문제에 관하여([코딩테스트 연습] 행렬 테두리 회전하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lastella/코딩테스트-연습-행렬-테두리-회전하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)