[프로그래머스/Java] Lv2-행렬 테두리 회전하기

Lv2-행렬 테두리 회전하기

문제 바로가기

문제

문제 설명
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 함수를 완성해주세요.

제한사항
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 배열.
초기 상태: $rows \times columns$ 크기의 행렬에 1부터 순서대로 숫자가 채워져 있다.
동작: queries에 주어진 직사각형 범위 (x1, y1, x2, y2)의 테두리 부분만 시계 방향으로 한 칸씩 회전시킨다.
출력: 각 회전마다 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 리턴한다.

접근 방식

1) 1-based Indexing 활용
문제에서는 좌표가 (1, 1)부터 시작한다. 보통 자바 배열은 0부터 시작하기 때문에 매번 -1을 해줘야 하는데, 이는 코드를 복잡하게 만들고 실수를 유발한다.

해결: 아예 배열을 new int[rows + 1][columns + 1]로 선언해서 문제의 좌표(1~rows, 1~columns)를 그대로 인덱스로 사용했다. (0번 인덱스는 버림)

2) 회전 로직: '밀기'가 아니라 '당기기'
테두리를 시계 방향으로 회전시켜야 한다. 직관적으로는 값을 시계 방향으로 밀어넣고 싶지만, 코드로 구현할 때는 빈 공간으로 값을 하나씩 당겨오는(Pull) 방식이 훨씬 구현하기 편하다.

시작점 저장: 왼쪽 상단 (x1, y1) 값을 temp 변수에 따로 빼둔다. (이곳이 빈 공간이 된다고 가정)

좌측 열 이동(↑): 아래쪽 값들을 위로 당긴다.

하단 행 이동(←): 오른쪽 값들을 왼쪽으로 당긴다.

우측 열 이동(↓): 위쪽 값들을 아래로 당긴다.

상단 행 이동(→): 왼쪽 값들을 오른쪽으로 당긴다.

마무리: 처음에 빼둔 temp 값을 (x1, y1+1) 위치에 집어넣는다.

최솟값 갱신: 값이 이동할 때마다 min 값을 갱신하여 정답을 찾는다.

코드

import java.util.*;

class Solution {
    public int[] solution(int rows, int columns, int[][] queries) {
        int size = queries.length;
        int[] answer = new int[size];
        int[][] arr = new int[rows+1][columns+1];

        int value = 1;
        for(int i=1; i<=rows; i++) {
            for(int j=1; j<=columns; j++) {
                arr[i][j] = value++;
            }
        }

        int idx = 0;
        for(int[] quer : queries) {
            int x1 = quer[0];
            int y1 = quer[1];
            int x2 = quer[2];
            int y2 = quer[3];
            
            int min = Integer.MAX_VALUE;
            
            int temp = arr[x1][y1];
            min = Math.min(min, temp);
            for(int i = x1; i < x2; i++) {
                arr[i][y1] = arr[i+1][y1];
                min = Math.min(min, arr[i+1][y1]);
            }
            
            for(int i=y1; i<y2; i++) {
                arr[x2][i] = arr[x2][i+1];
                min = Math.min(min, arr[x2][i+1]);
            }
            
            for(int i=x2; i>x1; i--) {
                arr[i][y2] = arr[i-1][y2];
                min = Math.min(min, arr[i-1][y2]);
            }
            
            for(int i=y2; i>y1; i--) {
                arr[x1][i] = arr[x1][i-1];
                min = Math.min(min, arr[x1][i-1]);
            }
            
            arr[x1][y1+1] = temp;
            
            answer[idx] = min;
            idx++;
        }

        return answer;
        
    }
}

느낀점

1. 배열 초기화의 중요성 (ArrayIndexOutOfBoundsException)
   처음에 습관적으로 int[] answer = {}; 처럼 빈 배열로 초기화했다가 에러가 났다.

문제: {}로 초기화하면 크기가 0인 배열이 생성되므로 값을 넣을 공간이 없다.

해결: 알고리즘 문제에서 결과의 개수가 정해져 있다면(여기서는 queries.length), 반드시 new int[size] 형태로 크기를 확보하고 시작해야 함을 다시 상기했다.

2. 좌표계 통일 (0-based vs 1-based)
   문제는 (1,1)부터 시작하는데 코드는 (0,0)부터 시작하면, x1-1, y1-1 처럼 보정하는 코드가 많아져서 가독성이 떨어지고 실수가 잦아진다. 이번 풀이처럼 메모리를 조금 더 쓰더라도 new int[rows+1][columns+1] 로 선언하여 문제의 좌표를 그대로 사용하는 방식이 훨씬 직관적이고 버그를 줄이는 방법임을 느꼈다.

3. 구현 문제의 팁
   회전 문제는 머릿속으로 시뮬레이션하기 벅찰 때가 있다.

시계 방향 회전 = 반시계 방향으로 값 당겨오기

이 공식을 기억해두면, 복잡한 임시 변수 교환 없이 temp 변수 하나로 깔끔하게 처리할 수 있다.