[JAVA] 프로그래머스 LEVEL2 행렬 테두리 회전하기

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

프로그래머스

코딩테스트 연습 > 2021 Dev-Matching: 웹 백엔드 개발자(상반기) > 행렬 테두리 회전하기

 

난이도: LEVEL2

알고리즘 유형: 구현

풀이 설명

로직은 간단하다.

시계 방향으로 값을 큐에 넣고 큐에 넣기 시작한 시작 좌표로 돌아오면 끝난다. 

이제 큐에서 꺼내서 값을 회전 시키는데 기존 시작 좌표 보다 이동 가능한 1템포 빠른 좌표에서 시작한다.

 

시작 좌표 보다 1칸 오른쪽이 아니라 왜 1템포가 빠른 좌표라고 설명한 이유?

 

만약 quey가 (1,1, 1,1) 이렇게 회전이 없는 경우나 

query(1,1, 2,1) 이렇게 세로로 회전하는 경우는 
오른쪽에서 시작하면 잘못 시작한다.  즉 회전 경로가 아닌 곳에서 시작하게 된다.

 

정답 코드 

import java.util.*;
class Solution {
    static int [] answer;
    static int [][] map;
    static int [] arx = {0,1,0,-1};
    static int [] ary = {1,0,-1,0};
    static Queue<Integer> q = new LinkedList<>();
    public int[] solution(int rows, int columns, int[][] queries) {
        answer = new int [queries.length];
        int cnt = 1;
        map = new int [rows][columns];
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < columns; j++){
                map[i][j] = cnt++;
            }
        }
        for(int i = 0; i < queries.length; i++){
            rotateAndFindMin(queries[i], i);
        }
        return answer;
    }
    public static void rotateAndFindMin(int [] query, int index){
        int x = query[0] - 1; 
        int y = query[1] - 1;
        int sx = x;
        int sy = y;
        int ex = query[2];
        int ey = query[3];
        int min = map[x][y];
        
        q.add(map[x][y]);
        
        for(int i = 0; i < 4; i++){
            while(true){
                int nx = x + arx[i];
                int ny = y + ary[i];
                if(sx <= nx && sy <= ny && nx < ex && ny < ey){
                    if(nx != sx || ny != sy){
                        q.add(map[nx][ny]);  
                        min = Math.min(min, map[nx][ny]);
                    }
                    x = nx; y = ny;
                }
                else break;
            }    
        }
        x = sx; y = sy;
        for(int i = 0; i < 4; i++){
            while(!q.isEmpty()){
                int nx = x + arx[i];
                int ny = y + ary[i];
                if(sx <= nx && sy <= ny && nx < ex && ny < ey){
                    map[nx][ny] = q.poll();
                    x = nx; y = ny;
                }
                else break;
            }    
        }
        answer[index] = min;
    }
}