행렬 테두리 회전하기

본 풀이는 java 언어를 사용하였습니다.
문제 보러가기

풀이

처음에는 실제 회전을 하지 않고도 값을 구할 수 있지 않을까 싶었는데,
숫자를 움직이면서 최소값을 구하다보니 회전 범위에 따라 값이 계속 바뀌니 실제 회전을 시켜야 겠구나 싶었다.

먼저 아래와 같이 숫자를 초기화 한 board 를 만들어준다.

public Integer[] solution(int rows, int columns, int[][] queries) {
    int[][] board = createBoard(rows, columns);
}

private int[][] createBoard(int rows, int columns) {
    int[][] board = new int[rows][columns];
    int no = 1;
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            board[i][j] = no++;
        }
    }
    return board;
}

그 후 query 범위에 따라서 값을 회전하는 로직을 추가해준다.

private void rotate(int[][] board, int[] query) {
    // 배열은 인덱스 0 부터 시작하니, 값을 1 빼준다.
    int startX = query[0] - 1;
    int startY = query[1] - 1;
    int endX = query[2] - 1;
    int endY = query[3] - 1;

    int[] boardTop = new int[endY - startY + 1]; // 상
    int[] boardBottom = new int[endY - startY + 1]; // 하
    for (int i = 0; i < boardTop.length; i++) {
        boardTop[i] = board[startX][startY + i];
        boardBottom[i] = board[endX][startY + i];
    }

    int[] boardLeft = new int[endX - startX + 1]; // 좌
    int[] boardRight = new int[endX - startX + 1]; // 우
    for (int i = 0; i < boardRight.length; i++) {
        boardLeft[i] = board[startX + i][startY];
        boardRight[i] = board[startX + i][endY];
    }
...
}

회전을 편하게 하기 위해 회전하기 전, 상 하 좌 우 숫자들을 각각의 1차원 배열로 넣어준다.
회전 반경이 아래와 같다면..

상 하 좌 우 값은 아래 값이 들어가게 된다.

• boardTop : [8, 9, 10]
• boardBottom : [26, 27, 28]
• boardLeft : [8, 14, 20, 26]
• boardRight : [10, 16, 22, 28]

위 배열들 값 중에서 가장 작은 값을 구해야 하므로 각각의 배열 최소값을 구한 후 result 에 넣어준다.

    ...

    int minTop = Arrays.stream(boardTop)
                       .min()
                       .getAsInt();
    int minBottom = Arrays.stream(boardBottom)
                          .min()
                          .getAsInt();
    int minLeft = Arrays.stream(boardLeft)
                          .min()
                          .getAsInt();
    int minRight = Arrays.stream(boardRight)
                          .min()
                          .getAsInt();

    result.add(Math.min(Math.min(minTop, minBottom), Math.min(minLeft, minRight)));

    ...
}

그 후 board 를 시계방향으로 1칸 씩 회전을 시켜준다.

    ...

    int index = 0;
    for (int i = startY; i < endY; i++) {
        board[startX][i + 1] = boardTop[index]; // 상
        board[endX][i] = boardBottom[index + 1]; // 하
        index++;
    }
    index = 0;
    for (int i = startX; i < endX; i++) {
        board[i][startY] = boardLeft[index + 1]; // 좌
        board[i + 1][endY] = boardRight[index]; // 우
        index++;
    }
}

위 과정을 풀어쓰자면 다음과 같다.
먼저 상단과 하단 부분을 옮겨준다. ( ☐ : 바꾸지 않은 공간 )

☐ 8 9
...
...
27 28 ☐

그 후 좌 우 부분을 옮겨준다.

14  8  9
20    10
26    16
27 28 22

위 처럼 해주면 한칸씩 회전하게 된다.
이제 queries 배열만큼 회전을 반복해주면서 최소값을 구하면 답이 나오게 된다.

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

    private List<Integer> result;

    public Integer[] solution(int rows, int columns, int[][] queries) {
        int[][] board = createBoard(rows, columns);
        result = new ArrayList<>();

        for (int[] query : queries) {
            rotate(board, query);
        }

        return result.toArray(new Integer[0]);
    }

    private void rotate(int[][] board, int[] query) {
        int startX = query[0] - 1;
        int startY = query[1] - 1;
        int endX = query[2] - 1;
        int endY = query[3] - 1;

        int[] boardTop = new int[endY - startY + 1]; // 상
        int[] boardBottom = new int[endY - startY + 1]; // 하
        for (int i = 0; i < boardTop.length; i++) {
            boardTop[i] = board[startX][startY + i];
            boardBottom[i] = board[endX][startY + i];
        }
        int[] boardLeft = new int[endX - startX + 1]; // 좌
        int[] boardRight = new int[endX - startX + 1]; // 우
        for (int i = 0; i < boardRight.length; i++) {
            boardLeft[i] = board[startX + i][startY];
            boardRight[i] = board[startX + i][endY];
        }

        int minTop = Arrays.stream(boardTop)
                           .min()
                           .getAsInt();
        int minBottom = Arrays.stream(boardBottom)
                              .min()
                              .getAsInt();
        int minLeft = Arrays.stream(boardLeft)
                              .min()
                              .getAsInt();
        int minRight = Arrays.stream(boardRight)
                              .min()
                              .getAsInt();

        result.add(Math.min(Math.min(minTop, minBottom), Math.min(minLeft, minRight)));

        int index = 0;
        for (int i = startY; i < endY; i++) {
            board[startX][i + 1] = boardTop[index]; // 상
            board[endX][i] = boardBottom[index + 1]; // 하
            index++;
        }
        index = 0;
        for (int i = startX; i < endX; i++) {
            board[i][startY] = boardLeft[index + 1]; // 좌
            board[i + 1][endY] = boardRight[index]; // 우
            index++;
        }
    }

    private int[][] createBoard(int rows, int columns) {
        int[][] board = new int[rows][columns];
        int no = 1;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] = no++;
            }
        }
        return board;
    }
}

회고

테두리 부분만 회전시키는 것을 생각하기가 되게 어려웠는데,
위처럼 회전하기 전의 4 변을 배열로 만들어 두고 한 변씩 숫자를 옮겨주면 쉽게 회전이 가능했다.
다만 코드가 좀 지저분해지는건 마음에 안들긴 했다..
푸는데 좀 오래걸리긴 했지만 내손으로 풀었다는 것에 뿌듯.