행렬 테두리 회전하기

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/77485

풀이

2차원 배열의 일부분을 회전하는 로직을 직접 구현해야하는 문제입니다.

아이디어를 떠올리는 부분은 어렵지 않으나 직접 구현하는데 있어 어려움이 있을 수 있습니다.

대략적인 구현 순서는 아래와 같습니다.

1. 1부터 n x m의 숫자가 들어있는 2차원 배열을 생성한다.
2. 주어진 queries를 순회하며, 시계 방향 회전 로직을 1에서 생성한 2차원 배열에 적용한다.
3. 2를 수행하면서 최소힙 (min heap)에 회전 경로에 포함되는 숫자들을 저장한다.
4. queries에 대한 순회가 1회 끝날 때마다 3에서 만든 최소힙에서 가장 작은 숫자를 꺼내 정답 배열에 저장한다.

먼저 1에 대한 구현입니다.

int[][] board = new int[rows][columns];

int n = 1;
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < columns; j++) {
        board[i][j] = n++;
    }
}

다음은 2 ~ 4에 대한 구현입니다.

회전을 적용하는 과정에서 직접 board를 수정할 경우 회전이 적용된 위치에 덮어써지는 값을 찾을 수 없으므로 board를 카피한 copyBoard를 이용합니다.

그리고 각 회전 단계에서 필요한 값은 회전 경로에 있는 값들 중 가장 작은 값이므로 최소힙을 만들고 활용합니다.

for (int k = 0; k < queries.length; k++) {
    int[][] copyBoard = new int[rows][columns];
    for (int i = 0; i < rows; i++) {
        System.arraycopy(board[i], 0, copyBoard[i], 0, columns);
    }

    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    int[] query = queries[k];
    int x1 = query[1] - 1;
    int x2 = query[3] - 1;
    int y1 = query[0] - 1;
    int y2 = query[2] - 1;

    for (int i = y1; i <= y2; i++) {
        for (int j = x1; j <= x2; j++) {
            if (i > y1 && i < y2 && j > x1 && j < x2)
                continue;

            minHeap.add(board[i][j]);

            // x+1 rotate
            if (i == y1 && j < x2) {
                copyBoard[i][j + 1] = board[i][j];
            }
            // y+1 rotate
            else if (i != y2 && j == x2) {
                copyBoard[i + 1][j] = board[i][j];
            }
            // x-1 rotate
            else if (i == y2 && j != x1) {
                copyBoard[i][j - 1] = board[i][j];
            }
            // y-1 rotate
            else {
                copyBoard[i - 1][j] = board[i][j];
            }
        }
    }

    Integer minNum = minHeap.peek();
    if (minNum != null) {
        answers[k] = minNum;
    }

    board = copyBoard;
}

마지막으로 전체 구현부에 대한 코드입니다.

import java.util.*;

class Solution {
    public int[] solution(int rows, int columns, int[][] queries) {
        int[] answers = new int[queries.length];

        int[][] board = new int[rows][columns];

        int n = 1;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                board[i][j] = n++;
            }
        }

        for (int k = 0; k < queries.length; k++) {
            int[][] copyBoard = new int[rows][columns];
            for (int i = 0; i < rows; i++) {
                System.arraycopy(board[i], 0, copyBoard[i], 0, columns);
            }

            PriorityQueue<Integer> minHeap = new PriorityQueue<>();

            int[] query = queries[k];
            int x1 = query[1] - 1;
            int x2 = query[3] - 1;
            int y1 = query[0] - 1;
            int y2 = query[2] - 1;

            for (int i = y1; i <= y2; i++) {
                for (int j = x1; j <= x2; j++) {
                    if (i > y1 && i < y2 && j > x1 && j < x2)
                        continue;

                    minHeap.add(board[i][j]);

                    // x+1 rotate
                    if (i == y1 && j < x2) {
                        copyBoard[i][j + 1] = board[i][j];
                    }
                    // y+1 rotate
                    else if (i != y2 && j == x2) {
                        copyBoard[i + 1][j] = board[i][j];
                    }
                    // x-1 rotate
                    else if (i == y2 && j != x1) {
                        copyBoard[i][j - 1] = board[i][j];
                    }
                    // y-1 rotate
                    else {
                        copyBoard[i - 1][j] = board[i][j];
                    }
                }
            }

            Integer minNum = minHeap.peek();
            if (minNum != null) {
                answers[k] = minNum;
            }

            board = copyBoard;
        }

        return answers;
    }
}

시간/공간 복잡도

시간 복잡도의 경우, queries의 길이 q x n x m (n, m은 열과 행의 크기) = O(qnm)이 됩니다.

공간 복잡도의 경우 n x m 2차원 배열의 크기인 O(nm)이 됩니다.