백준 16927번: 배열 돌리기 2 (JAVA)

 

문제

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

 

---

 

풀이

설명을 위해, 배열에 대하여 layer을 다음과 같이 정의한다:

1	1	1	1	1	1
1	2	2	2	2	1
1	2	3	3	2	1
1	2	3	3	2	1
1	2	2	2	2	1
1	1	1	1	1	1

같은 숫자로 표시한 곳이 같은 layer라고 하자. 위와 같은 방식으로 M*N 배열에서도 layer를 정의할 수 있다.

 

풀이 1. 빡구현으로(index에서 실수하기 매우 쉬움!) 배열에서 돌려서 푼다. 각 껍질(아래 표 참고)마다 R을 (2*가로길이 + 2*세로길이 - 4)로 나눈 나머지만큼 회전시킨다. 왜냐? 주기가 (2*가로길이 + 2*세로길이 - 4)이기 때문이다. 모듈러 계산만 했다면 시간 내로 풀릴 것이다.

풀이 2. 회전 한 번이 (2*가로길이 + 2*세로길이 - 4)만큼의 연산이 들어간다는 점이 비효율적으로 느껴져서, 각 layer의 원소를 큐에 넣어준 후, queue에서 dequeue한 값을 enqueue하면 회전 한 번에 연산 2번으로 끝날 것이라 생각했다. 일단 배열을 저장한 후, 각 layer를 따라 각각의 원소를 올바른 queue에 넣어준 후, 돌리는 연산을 수행한 후(마찬가지로 R을 (2*가로길이 + 2*세로길이 - 4)로 나눈 나머지만큼만 돌려준다.), 각 layer를 따라 큐에서 dequeue하여 회전 연산한 값을 배열에 넣어주었다.

풀이 1이 Worst Case O(MN*max(M, N))이고, 풀이 2는 Worst case O(MN) time complexity를 가질 것이다.

 

코드

풀이 1

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

public class Main {
	static int[][] array;
	
	public static void main(String[] args) throws IOException {
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		long R = Long.parseLong(st.nextToken());
		int start = 0;
		array = new int[M][N];
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				array[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		while (2*start + 1 < M && 2*start + 1 < N) {
			for (int i = 0; i < (R % (2*M+2*N-8*start-4)); i++) {
				rotate(start, M-start, N-start);
			}
			start++;
		}

		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				sb.append(array[i][j]+" ");
			}
			sb.append("\n");
		}
		sb.setLength(sb.length()-1);
		System.out.println(sb);
	}
	
	
	public static void rotate(int start, int M, int N) {
		int temp = array[start][start];
		for (int j = start+1; j < N; j++) {
			array[start][j-1] = array[start][j];
		}
		for (int i = start+1; i < M; i++) {
			array[i-1][N-1] = array[i][N-1];
		}
		for (int j = N-2; j > start-1; j--) {
			array[M-1][j+1] = array[M-1][j];
		}
		for (int i = M-2; i > start; i--) {
			array[i+1][start] = array[i][start];
		}
		array[start+1][start] = temp;
	}
}

 

풀이 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static List<ArrayDeque<Integer>> queueList = new ArrayList<ArrayDeque<Integer>>();
	static int[][] array;
	
	public static void main(String[] args) throws IOException {
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		long R = Long.parseLong(st.nextToken());
		int start = 0;
		array = new int[M][N];
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				array[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		while (2*start + 1 < M && 2*start + 1 < N) {
			ArrayDeque<Integer> temp = new ArrayDeque<Integer>();
			for (int j = start; j < N - start; j++) {
				temp.offer(array[start][j]);
			}
			for (int i = start+1; i < M - start; i++) {
				temp.offer(array[i][N-1-start]);
			}
			for (int j = N-2-start; j > start-1; j--) {
				temp.offer(array[M-1-start][j]);
			}
			for (int i = M-2-start; i > start; i--) {
				temp.offer(array[i][start]);
			}
			queueList.add(temp);
			start++;
		}
		
		start = 0;
		while (2*start + 1 < M && 2*start + 1 < N) {
			rotate(start, (R % (2*M + 2*N - 8*start - 4)));
			start++;
		}
		
		start = 0;
		
		while (2*start + 1 < M && 2*start + 1 < N) {
			for (int j = start; j < N - start; j++) {
				array[start][j] = queueList.get(start).poll();
			}
			for (int i = start+1; i < M - start; i++) {
				array[i][N-1-start] = queueList.get(start).poll();
			}
			for (int j = N-2-start; j > start-1; j--) {
				array[M-1-start][j] = queueList.get(start).poll();
			}
			for (int i = M-2-start; i > start; i--) {
				array[i][start] = queueList.get(start).poll();
			}
			start++;
		}
		
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				sb.append(array[i][j]+" ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb);
	}
	
	
	public static void rotate(int index, long R) {
		for (int i = 0; i < R; i++) {
			queueList.get(index).offer(queueList.get(index).poll());
		}
	}
}

 

성능 비교

풀이 1이 572ms, 풀이 2가 424ms가 나왔다. 그렇게 유의미한 차이는 아니나, M, N이 커지면 더 차이가 날 거라 생각한다.

 

P.S.

배열 왜 N*M으로 제시하는 지 모르겠네.. 행렬은 M*N이지.