[HackerRank] Matrix Layer Rotation

출처: https://www.hackerrank.com/challenges/matrix-rotation-algo/problem

 Input 

4 4 2

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

　 

 Output 

3 4 8 12

2 11 10 16

1 7 6 15

5 9 13 14

Cycle의 개수는 m, n 중 작은 수의 2로 나누었을 때의 몫이다. 

ex) min (2 * 6) → 2 / 2 = 1 

    min (8 * 9) → 8 / 2 = 4

위와 같이 m, n 중 큰 수가 어떤 수든 상관없이 『min( m, n ) / 2』로 계산해서

cycle 개수를 도출할 수 있다.

 

실제 이차원 배열상에서 rotation을 시킬 수도 있지만

『ㅁ』 을 한 개의 『ㅡ』로 생각하여 rotation 처리

Circle Queue를 이용해서 제일 마지막 원소를 앞으로 삽입시켜주는 방식으로 구현

 

조건 중 1 ≤ r ≤ 10^9

는 상당히 큰 숫자이므로 모든 테두리를 주먹구구 방식으로 rotation을 할 수는 없다.

(8 * 9 Matrix)

* 여러 cycle이 존재한다면 각 cycle의 시작지점은 (0,0), (1,1), (2,2)....

(1) (8 + 9) * 2 - 4 = 30번 회전에 한 바퀴 주기  

(2) (6 + 7) * 2 - 4 = 22번 

(3) (4 + 5) * 2 - 4 = 14번 

(4) (2 + 3) * 2 - 4 = 6번 

(* 각 테두리를 『ㅡ』의 형태인 리스트에 보관했다면 리스트의 길이가 회전주기라고 볼 수 있다.)

 

r를 최소화하는 것에 대한 핵심은 다음과 같다.

실제 모든 cycle이 동시다발적으로 회전하지만 각 cycle마다 회전주기는 다르므로

최종 형태를 도출할 때는 각 cycle의 회전주기를 이용하여 최소한 회전시키는 것이다.

　

ex) 위의  (8 * 9 Matrix) 100번 회전 후의 형태는

- 100 % 30 = 10번만 회전

- 100 % 22 = 12번만 회전

- 100 % 14 = 2번만 회전

- 100 % 6 = 4번만 회전

이 경우, 처음 100 * 4번 수행하는 것보다 (10 + 12 + 2 + 4)번만큼만 수행한 것과 같다.

　

구현 순서는 다음과 같다.

1. 이차원 배열에서 cycle 개수 도출

2. 각 cycle을 리스트형태로 변형

3. 각 cycle마다 회전 횟수 재조정 후 회전

4. 회전 완료된 리스트를 이차원 배열형태로 변형

---

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int m = Integer.parseInt(sc.next());
        int n = Integer.parseInt(sc.next());
        int r = Integer.parseInt(sc.next());
         
        int[][] arr = new int[m][n];
        for(int x=0; x<m; x++) {
            for(int y=0; y<n; y++) {
                arr[x][y] = Integer.parseInt(sc.next());
            }
        }
        // 1. 주어진 배열이 몇개의 cycle로 구성할 수 있는지 확인
        int cycle = Math.min(m, n) / 2;
                   
        // 리스트가 여러개 필요하므로 이를 동적으로 제어하기 위해
        // 리스트 안에 리스트를 넣어둠
        List<ArrayList<Integer>> cycleList = new ArrayList<ArrayList<Integer>>();
        for(int c=0; c<cycle; c++) {
            ArrayList<Integer> temp = new ArrayList<>();
            cycleList.add(temp);
        }
         
        // 2. 각 cycle(테두리)을 각각의 리스트에 보관하여 한 줄로 표시
        // cycle 방향으로 집어 넣을 수 있도록(하우상좌)
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
         
        for(int c=0; c<cycle; c++) {
            // 바깥쪽 테두리(cycle)부터 보관 (반시계 방향 탐색)
            ArrayList<Integer> temp = cycleList.get(c);
            // 각 cycle(테두리)의 시작 지점
            int x = c;
            int y = c;
             
            // 시작 지점을 리스트에 먼저 넣어둔다.
            // (시작지점은 -1로 표시안해도 탐색에 지장x)
            temp.add(arr[x][y]);
             
            // 탐색하면서 리스트에 값 저장
            for(int d=0; d<dx.length; d++) {
                // 특정 방향의 끝지점 까지
                while(true) {
                    x = x + dx[d];
                    y = y + dy[d];
                    if(x < 0 || y < 0 || x >= m  || y >= n) {
                        // 이어서 탐색하기 위해 배열 벗어난 index 재조정
                        x = x - dx[d];
                        y = y - dy[d];
                        break;
                    }
                    // 한바퀴 돌면서 시작 지점에 돌아왔으면 stop
                    // (for문이 다 수행된 순간)
                    if(x == c && y == c) {
                        break;
                    }
                     
                    // 제일 바깥쪽 테두리는 상관 없지만.
                    // 안쪽 테두리들은 바깥쪽 테두리를 침범하지 않으면서 탐색해야 한다.
                    // 즉 범위를 좁혀가야 하므로 탐색 표시를 음수(-1)로 표시
                    if(arr[x][y] == -1) {
                        // 이어서 탐색하기 위해 배열 벗어난 index 재조정
                        x = x - dx[d];
                        y = y - dy[d];
                        break;
                    }
                    // 해당 값 저장
                    temp.add(arr[x][y]);
                    // 탐색 표시
                    arr[x][y] = -1;
                }
            }
        }
                 
        // 3. r이 클 수 있기 때문에 각 테두리별로 회전 주기를 분석하여 맞춰준다.
        for(int i=0; i<cycleList.size(); i++) {
            ArrayList<Integer> temp = cycleList.get(i);
            // 해당 테두리 회전주기를 분석
            int rotation = r % temp.size();
            // 각 cycle(테두리) 회전 시작
            while(rotation-- > 0) {
                // 제일 뒤의 원소를 앞쪽으로 배치
                temp.add(0, temp.remove(temp.size()-1));    
            }    
        }
         
        // 4. 회전이 끝난 후 배열에 맞에 다시 재배치
        for(int c=0; c<cycle; c++) {
            // 바깥쪽 테두리(cycle)부터 재배치
            ArrayList<Integer> temp = cycleList.get(c);
            // 각 cycle(테두리)의 시작 지점
            int x = c;
            int y = c;
             
            // 시작 지점에 리스트의 제일 앞 원소부터 집어 넣는다.
            arr[x][y] = temp.remove(0);
             
            // 달팽이 모양으로 탐색
            for(int d=0; d<dx.length; d++) {
                // 특정 방향의 끝지점 까지
                while(true) {
                    x = x + dx[d];
                    y = y + dy[d];
                    if(x < 0 || y < 0 || x >= m  || y >= n) {
                        // 이어서 탐색하기 위해 배열 벗어난 index 재조정
                        x = x - dx[d];
                        y = y - dy[d];
                        break;
                    }
                    // 한바퀴 돌면서 시작 지점에 돌아왔으면 stop
                    // (for문이 다 수행된 순간)
                    if(x == c && y == c) {
                        break;
                    }
                     
                    // 제일 바깥쪽 테두리는 상관 없지만.
                    // 안쪽 테두리들은 바깥쪽 테두리를 침범하지 않으면서 탐색해야 한다.
                    // 역으로 음수 여부를 판단하면서 탐색
                    if(arr[x][y] != -1) {
                        // 이어서 탐색하기 위해 배열 벗어난 index 재조정
                        x = x - dx[d];
                        y = y - dy[d];
                        break;
                    }
                    arr[x][y] = temp.remove(0);
                }
            }
        }
         
        // 정답 출력
        for(int x=0; x<m; x++) {
            for(int y=0; y<n; y++) {
                System.out.print(arr[x][y] +" ");
            }
            System.out.println();
        }
    }
}