(Java) Programmers 행렬 테두리 회전하기 (Queue, Matrix Rotate)

 

 

- 목차

 

문제 설명.

 

아래 링크는 "프로그래머스 행렬 테스트 회전하기" 문제의 웹 링크입니다.

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

프로그래머스

 

 

rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.

• x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.

다음은 6 x 6 크기 행렬의 예시입니다.

 

 

문제 분석.

행렬의 특정 영역을 순회하면서 행렬의 값을 Swap 하는 문제입니다.

저는 이 문제는 해결하기 위해서 Queue 사용하였구요.

행렬을 회전하기 위해서 While 반복문을 사용하였습니다.

두 번의 회전을 하는데,

첫 번째 회전에서 값들을 Queue 에 추가합니다.

그리고 두번째 회전에서 1칸씩 Swap 합니다.

그리고 최소값을 간단하게 구하기 위해서 PriorityQueue 를 사용하였습니다.

 

 

문제 풀이.

 

import java.util.*;

class Solution {
    public int[] solution(int rows, int columns, int[][] queries) {
        
        // 초기화
        int[] answer = new int[queries.length];
        int[][] map = new int[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                map[i][j] = (columns) * (i) + (j + 1);
            }
        }
    
        for (int i = 0; i < queries.length; i++) {
            int[] query = queries[i];
            
            // Swap 하기 위한 queue
            Queue<Integer> queue = new LinkedList();
            
            // 최소값을 구하기 위한 Queue
            PriorityQueue<Integer> heap = new PriorityQueue();
            
            
            int startY = query[0] - 1;
            int startX = query[1] - 1;
            int endY = query[2] - 1;
            int endX = query[3] - 1;
            
            int curX = startX + 1;
            int curY = startY;
            
            queue.add(map[startY][startX]);
            heap.add(map[startY][startX]);
            
            // 1회 회전하면서 모든 값들을 Queue, PriorityQueue 에 추가합니다. 
            while (!(curX == startX && curY == startY)) {
                queue.add(map[curY][curX]);
                heap.add(map[curY][curX]);
                int[] next = rotate1Step(curY, curX, startY, startX, endY, endX);
                curY = next[0];
                curX = next[1];
            }
            
            curX = startX + 1;
            curY = startY;
            
            // 1회 회전하면서 값은 Swap 합니다. 
            while (!queue.isEmpty()) {
                map[curY][curX] = queue.poll();
                int[] next = rotate1Step(curY, curX, startY, startX, endY, endX);
                curY = next[0];
                curX = next[1];
            }
            
            answer[i] = heap.poll();
        }
        return answer;
    }
    
    // 다음 x, y 좌표를 반환합니다. 
    int[] rotate1Step (int curY, int curX, int startY, int startX, int endY, int endX) {
        if (curY == startY)  {
            // 첫번째 끝
            if (curX == endX) curY++;
            else curX++;
        }
        // 두번째 끝
        else if (curX == endX)  {
            if (curY == endY) curX--;
            else curY++;
        }
        // 세번째 끝
        else if (curY == endY)  {
            if (curX == startX) curY--;
            else curX--;
        }
        // 4번째 끝
        else if (curX == startX)  {
            if (curY == startY) curX++;
            else curY--;
        }
        
        return new int[]{curY, curX};
    }
}