[BOJ] 16927. 배열돌리기2 - Simulation

[BOJ] 16927. 배열돌리기2 - Simulation

제출일 : 2019-10-20

문제 풀이 시간 : 15M

난이도 : ★

Problem

link : https://www.acmicpc.net/problem/16927

Input

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

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

Output

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

Constraints

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 10^9
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 10^8

Solution & Inpression

시뮬레이션 문제

배열돌리기1 문제에서 회전수 R이 커진 문제

최적화 문제로 각각의 사각형마다 회전후 제자리가 되는 부분을 제외하고 돌리는 방법으로 문제를 해결하였다.

그래도 메모리와 시간은 폭발하는데.......

쉽지 않다....

Code

언어 : JAVA

메모리 : 105,660 kb

실행시간 : 1,388 ms

import java.util.Scanner;

public class Main {
    static int N, M, SR, S;
    static int[][] matrix, copy;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt(); // 배열의 크기 N*M
        M = sc.nextInt();
        SR = sc.nextInt(); // 회전 수 R

        // min(N, M) mod 2 = 0
        S = Math.min(N, M) / 2; // 1회전에서 돌려야하는 사각형의 개수

        matrix = new int[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        spin();
        print();
    }

    private static void print() {
        for (int[] is : matrix) {
            for (int i : is) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

    static void spin() {
        for (int s = 0; s < S; s++) {
            int T = s;
            int B = N - 1 - s;
            int R = M - 1 - s;
            int L = s;
            int r = SR % (2 * (R-L+1) + 2 * (B-T+1) - 4);
            //System.out.println(r);
            while (r-- != 0) {
                int tmp = matrix[s][s];
                for (int i = L; i < R; i++)
                    matrix[T][i] = matrix[T][i + 1];
                for (int i = T; i < B; i++)
                    matrix[i][R] = matrix[i + 1][R];
                for (int i = R; i > L; i--)
                    matrix[B][i] = matrix[B][i - 1];
                for (int i = B; i > T; i--)
                    matrix[i][L] = matrix[i - 1][L];
                matrix[T + 1][L] = tmp;

            }
        }
    }
}