[프로그래머스] 행렬 테두리 회전하기 문제 풀이 java

1. 문제 설명

문제 링크

(1) 회전 시킬 부분 행렬의 좌상단, 우하단의 List가 주어진다.
(2) List의 값마다 행렬을 시계 방향으로 회전시킨다.
(3) 회전할 때, 움직였던 값 중 가장 작은 값들을 모아서 반환한다.

2. 접근 방식

KEY WORD: BRUTE FORCE, 배열 회전

배열 회전은 브루트 포스 문제를 풀 때 단골로 나온다. 코딩 테스트에서도 배열 회전이라는 키워드가 단독으로 문제에 나오지 않지만, 문제의 조연으로는 자주 등장했던 것 같다. 그래서 회전하는 법에 대해 알아두는 것은 중요하다.

문제에서, 회전하는 모습을 친절하게 예시로 알려준다.

14 -> 8의 자리로, 8이 9의 자리로 시계 방향으로 움직이고 있음을 볼 수 있다.
그렇다면 구현을 할 때는 어떻게 해야할까? 구현할 때는 반 시계 방향으로 움직여야 한다. 이유는 다음과 같다.

map[2][2] = map[3][2];
map[3][2] = map[4][2];
// ...

우리가 생각하는 회전이 나아가는 방향과 달리, 대입은 역 방향으로 이루어지기 때문이다.
위의 예시의 14 -> 8, 8 -> 9가 되려면, 9의 행렬에 8대입 -> 8의 행렬에 14 대입으로 역순으로 가야한다.
근데 이렇게 하면 문제가 생긴다. 위의 예시 대로 하면

9 자리는 8이 들어와야 하지만, 이미 원래 8의 자리가 14로 바뀐 뒤라서, 14가 두 번 쓰이게 된다. 이러한 문제점에서 벗어나기 위해, 최초 값의 대입이 이루어지는 8 부분은 미리 빼두어서 가지고 있어야 한다.

3. 코드 풀이

import java.io.*;
import java.util.*;

class Solution {
    public int[] solution(int rows, int columns, int[][] queries) {
        int [][] map = new int [rows][columns];
        int k = 1;
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < columns; j++){
                map[i][j] = k++;
            }
        }    

        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < queries.length; i++){
            list.add(rotation(queries[i][0]-1,queries[i][1]-1,queries[i][2]-1,queries[i][3]-1, map));
        }

        return list.stream().mapToInt(x->x).toArray();

    }

    public int rotation(int x1, int y1, int x2, int y2, int [][] map){

        int [][] d = new int [][]{{1,0},{0,1},{-1,0},{0,-1}};
        int temp = map[x1][y1];
        int ans  = temp;
        map[x1][y1] = map[x1+1][y1];
        int nowX = x1+1; int nowY = y1;
        int i = 0;
        while(nowX != x1 || nowY != y1) {
            ans = Math.min(ans, map[nowX][nowY]);
            if(nowX+d[i][0] > x2 || nowY+d[i][1] > y2 || nowX+d[i][0] < x1 || nowY+d[i][1] < y1){
                i = (i+1)%4;
            }
            int nx = nowX + d[i][0];
            int ny = nowY + d[i][1];
            map[nowX][nowY] = map[nx][ny];
            nowX = nx; nowY = ny;
        }
        map[nowX][nowY+1] = temp;

        return ans;
    }
}