백준 16927 - 배열 돌리기 2

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번 회전시킨 결과를 구해보자.

접근 방법

배열 돌리기1에서 시간을 더 단축하여 효율 적인 코드를 작성하라고 요구하는 문제이다.
배열 돌리기1 코드에서 비효율 적인 부분이 무엇인가 고민한 결과, 문제에서 요구하는 반복 횟수가 커짐에 따라 불필요한 회전이 있다는 것을 알았다.
예를들어 4x4의 배열에서 r이 13으로 주어져, 13바퀴를 돌도록 문제가 주어지면
4x4의 제일 바깥 테두리 크기가 12이므로, 결국 한번만 이동한 것과 같은 결과이다.

따라서 각 테두리 변의 크기에 따라 반복 횟수를 modulo 해주어, 불필요한 회전 수를 줄인다.

구현

이전 문제에서는 총 반복 횟수를 제일 바깥 반복으로 돌렸다면,
이제는 각 테두리에 해당하는 반복문 내부에, 회전 반복문을 옮긴다.
회전 반복 횟수를, 테두리 크기 만큼 modulo해준다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int dy[] = {0,1,0,-1};		// 우, 하, 좌, 상 
	static int dx[] = {1,0,-1,0}; 
    public static void main(String []args) throws IOException {        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	int n = stoi(stk.nextToken());
    	int m = stoi(stk.nextToken());
    	int r = stoi(stk.nextToken());
    	int arr[][] = new int[n][m];
    	int sm = Math.min(n, m);
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < m; j++)
    			arr[i][j] = stoi(stk.nextToken());
    	}
    	int i, j, d = 0, nr;
    	
		for(int idx = 0; idx < sm/2; idx++) {
			nr = r % ((n - idx * 2) * 2 + (m - idx * 2) * 2 - 4);		// 새롭게 추가한 코드. 해당하는 테두리의 크기를 modulo 해주어, 반복 횟수를 줄인다.  
			while(nr-- != 0) {
				i = idx;
				j = idx;
				d = 0;
				int tmp = arr[i][j];
				
				while(d != 4) {
					if(i + dy[d] < idx || i + dy[d] >= n - idx  || j + dx[d] < idx || j + dx[d] >= m - idx) {
						d++;
						continue;
					}
					arr[i][j] = arr[i + dy[d]][j + dx[d]];
					i += dy[d];
					j += dx[d];
				}
				arr[idx + 1][idx] = tmp;
			}
    	}
    	
    	StringBuilder sb = new StringBuilder();
    	for(int[] a : arr) {
    		for(int v : a) {
    			sb.append(v).append(" ");
    		}
    		sb.append("\n");
    	}
    	System.out.println(sb.toString());
    	br.close();
    }
    static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐★★★

후기

문제 조건인 행/열 최소 값은 2의 배수이다를 읽지 않아, 쓸데없이 고생했다.
문제를 잘 읽어라는 교수님 말씀이 뭔지 새삼 깨닫게된다 정말로,,

개선할 점

문제 좀 읽자!!!!