[Java] 16927 배열 돌리기 2

문제

문제
크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.

A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5]
   ↓                                       ↑
A[2][1]   A[2][2] ← A[2][3] ← A[2][4]   A[2][5]
   ↓         ↓                   ↑         ↑
A[3][1]   A[3][2] → A[3][3] → A[3][4]   A[3][5]
   ↓                                       ↑
A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5]
예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.

1 2 3 4       2 3 4 8       3 4 8 6
5 6 7 8       1 7 7 6       2 7 8 2
9 8 7 6   →   5 6 8 2   →   1 7 6 3
5 4 3 2       9 5 4 3       5 9 5 4
 <시작>         <회전1>        <회전2>
배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.

입력
첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

출력
입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

문제 풀이

이전 배열 돌리기 1과 문제는 같다 다만 조건이 달라졌는데 기존 1의 회전 수의 R의 최대 범위는 1000이었지만 2에선 2의 10승으로 바뀌었다. 기존의 코드로는 시간초과가 난다.

[Java] 16926 배열돌리기 1

 

시간을 줄이려면 회전 수를 줄여야한다. 어떻게 줄여야할까?

생각해보자 만약 100번 회전을 돌려야한다고 할 때 가장 바깥의 그룹이 9개의 노드를 가지고 있다고 생각해보자

9번 회전을 시키게 되었을 때 회전을 하긴 했지만 원래 모양과 다를 것이 없다.

18, 27.... 노드의 배수만큼 회전을 시켰을 경우에는 달라지는 것이 없기 때문에 (회전 수 % 그룹의 노드 수) 만큼만, 즉 회전 수에 그룹의 노드 수를 나눈 나머지만큼만 회전 시킨다면 원하는 결과를 얻으면서 회전 수는 크게 줄일 수 있다.

 

그렇다면 그룹의 노드 수는 어떻게 구할까? n + m을 더한 수에 곱하기 2를 하면 변의 길이가 나온다. 이 변의 길이 중 모서리의 길이의 중복을 피하기 위해 - 4를  해주면 가장 바깥의 노드 수가 나오게 된다. 예제2를 기준으로 설명하자면 4 + 5 * 2 = 18 => 18 - 4 = 14 이다. 즉 가장 바깥의 노드 수는 14개 이다. 그럼 그 안의 그룹의 노드 수는 어떻게 구할까?

n과 m의 크기를 - 2 씩 빼주면 된다. 즉 (2 + 3) * 2 - 4 = 6이 된다. 

공식화 해보자면 아래와 같다.

(N * 2) + (M * 2) - 4)
// 다음 그룹은 이전 그룹에서 모서리 노드 수를 빼준 만큼 있다.
N -= 2;
M -= 2;

 

이를 활용하기 위해서 기존 회전 수만큼 반복문을 실행해서 그룹별로 한 칸을 이동하는 메소드를 실행하는 배열돌리기1 형태로 하기보다는 그룹별로 메소드를 반복해서 회전 수 만큼 한 칸을 이동하는 메소드 형태로 그 구조를 변경한다.

 

자세한 로직은 주석으로 추가 설명한다.

자바 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class N16927 {
    private static int n, m, r;
    private static int group;
    private static int[][] arr;
    private static final int[] dr = {0, 1, 0, -1};
    private static final int[] dc = {1, 0, -1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());

        arr = new int[n][m];

        // 그룹의 수, n과 m중 작은 쪽의 나누기 2 한 값이 그룹의 수가 된다.
        group = Math.min(n,m) / 2;

        for(int i = 0; i < arr.length; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < arr[i].length; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int N = n;
        int M = m;
        // 그룹 수 만큼 실행
        for(int i = 0; i < group; i++) {
            // i는 그룹 번호, 뒤는 해당 그룹이 가진 노드의 수를 의미한다.
            // N + M * 2를 해주면 각 변의 길이를 다 더한 것이고 중복되는 모서리 노드의 수 4개를 빼준다.
            rotate(i, (N * 2) + (M * 2) - 4);
            // 다음 그룹은 이전 그룹에서 모서리 노드 수를 빼준 만큼 있다.
            N -= 2;
            M -= 2;
        }

        // 출력
        for(int[] arrA : arr){
            for(int i : arrA){
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

    public static void rotate(int start, int nodeCount){
        int x, y, idx;

        // 회전 수만큼 반복한다.
        // 노드 수 만큼 돌릴 경우 처음과 달라지는 것이 없기 때문에 굳이 계산에 넣지 않기 위해서
        // 그룹의 노드수 만큼 나눠준 나머지 값만큼 돌린다.
        // 나머지만큼만 돌리면 최대로 노드 수 - 1 만큼만 회전하기 때문에 시간이 많이 단축된다.
        for(int i = 0; i < r % nodeCount; i++){
            // 그룹 시작 인덱스 x, y
            // 1그룹이면 0,0 2그룹이면 1,1 등으로 시작한다.
            x = start;
            y = start;

            // 처음의 인덱스 값을 미리 빼놓는다.
            // 맨 마지막에 start+1, start 인덱스 위치에 삽입해준다.
            int temp = arr[start][start];

            // 방향 초기화
            idx = 0;
            // 4방향을 다 돌때까지 진행한다.
            // dr, dc에 따라서 우,하,좌,상 방향으로 탐색한다.
            while(idx < 4){
                // 현재 위치에서 우,하,좌,상 방향의 인덱스 위치를 얻는다.
                int nx = x + dr[idx];
                int ny = y + dc[idx];

                // 해당 인덱스 위치가 그룹의 범위를 벗어나지 않는 경우에 현 (x,y)에 (nx,ny)값을 넣어준다.
                // 예를 들자면 맨처음 0,0에서 시작하여 오른쪽 값(0,1 .... 0,m)을 확인하면서 넣어줄 것이다.
                // 그러다가 오른쪽 범위를 벗어나면 (0, m+1) 그때부터는 idx를 1 올려주어 아랫쪽으로 이동하는 것. (1, m)
                if(nx < n - start && ny < m - start && nx >= start && ny >= start){
                    arr[x][y] = arr[nx][ny];
                    x = nx;
                    y = ny;
                }else{
                    idx++;
                }
            }

            // 마지막으로 처음 빼놓았던 i,i 인덱스 위치의 값을 삽입한다.
            arr[start + 1][start] = temp;
        }
    }
}