[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번 회전시킨 결과를 출력한다.

제한

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 109
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 108

예제 입력 1

4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

예제 출력 1

3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14

예제 입력 2

5 4 7
1 2 3 4
7 8 9 10
13 14 15 16
19 20 21 22
25 26 27 28

예제 출력 2

28 27 26 25
22 9 15 19
16 8 21 13
10 14 20 7
4 3 2 1

예제 입력 3

2 2 3
1 1
1 1

예제 출력 3

1 1
1 1

 

소스코드

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

public class Main {

	private static int N, M, R;
	private static int[][] arr;
	private static int[][] result;
	
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		String s=bf.readLine();
		StringTokenizer st=new StringTokenizer(s, " ");
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		R=Integer.parseInt(st.nextToken());
		arr=new int[N][M];
		int cnt=Math.min(N,  M) / 2;
		
		for(int r=0;r<N;r++) {
			s=bf.readLine();
			st=new StringTokenizer(s, " ");
			for(int c=0;c<M;c++) arr[r][c]=Integer.parseInt(st.nextToken());
		}
		
		for(int d=0;d<cnt;d++) {
			int round=(N-1-2*d)*2+(M-1-2*d)*2; // 배열 돌리기 1에서 추가된 부분 
			int r=R%round; // 배열 돌리기 1에서 추가된 부분 
			for(int ro=0;ro<r;ro++) {
				rotate(d);
			}
		}
		
		for(int[] r:arr) {
			for(int c:r) System.out.print(c+" ");
			System.out.println();
		}
	}

	public static boolean isIn(int x, int y, int pos) {
		return x>=pos && x<N-pos && y>=pos && y<M-pos;
	}
	
	public static void rotate(int d) {
		int keep=arr[d][d];
		for(int c=d+1;c<M-d;c++) {
			arr[d][c-1]=arr[d][c];
		}
		for(int r=d+1;r<N-d;r++) {
			arr[r-1][M-d-1]=arr[r][M-d-1];
		}
		for(int c=M-d-2;c>=d;c--) {
			arr[N-d-1][c+1]=arr[N-d-1][c];
		}
		for(int r=N-d-2;r>=d+1;r--) {
			arr[r+1][d]=arr[r][d];
		}
		arr[d+1][d]=keep;
	}
}

배열 돌리기 시리즈 2번째 문제로, 배열 돌리기 1과 달리 R값의 범위가 매우 커졌습니다.

따라서 배열 돌리기 1과 같은 방식으로 해결하면 시간 초과가 발생하게 됩니다.

이를 해결하기 위해 배열이 원래 자리로 돌아왔을 경우 같은 값을 갖는다는 것을 이용하여 모듈러 연산을 적용해주었습니다. 모듈러 연산을 통해 R값을 줄여주는 부분을 추가해주면 시간 초과를 해결할 수 있습니다.

 

https://sujin7837.tistory.com/244?category=971822 

[Java] 백준 16926번 : 배열 돌리기 1