문제

BOJ 16927: 배열 돌리기 2 https://www.acmicpc.net/problem/16927

풀이

조건

• 1 <= R <= 10^9
• min(N, M) mod 2 = 0
  • 가로, 세로 중 더 짧은 값이 짝수라는 뜻이다.

    1 1 1 1 1 1　　　　　　　　　　　　　　　　　　1 1 1 1 1 1
    1 0 0 0 0 1　　　　　　　　　　　　　　　　　　1 0 0 0 0 1
    1 0 0 0 0 1　　　　　　　　　　　　　　　　　　1 1 1 1 1 1
    1 1 1 1 1 1
    <가능한 경우>　　　　　　　　　　　　　　　　<불가능한 경우>

• 반시계 방향으로 회전시킨다.

풀이 순서

• 회전시켜야하는 그룹 수 만큼 회전한다.
• 회전 메소드인 rotate()에 파라미터 2개를 전달한다.
  • start : 해당 그룹에서 회전을 시작하는 좌표
  • len : 해당 그룹에 있는 값 갯수
    • 처음엔 가장 바깥쪽 그룹에서 시작한다. ==> 2 X nN + 2 X nM - 4
      • 각 변의 길이를 모두 더하면 꼭지점에서 4가 추가로 계산되므로 4를 빼줬다.
    • 다음 그룹으로 넘어가면 각 변의 길이가 2씩 줄어들기 때문에 nN -= 2, nM -= 2 연산을 해준다.
  • rotate() 메소드 내부에서 회전시킬 횟수는 입력받은 회전 횟수 R에서 해당 그룹에 있는 값 갯수를 나눴을 때 나온 나머지이다.(int cir = R % len;)
    • 이 부분이 시간 초과가 나지 않도록 하는 부분이다.
  • 이 후 값들을 회전시키는 로직은 아래 코드에서 주석을 보는 것이 더 쉽다.

코드

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

public class Main {
    
	static int N, M, R;
	static int[][] map;
    
	static int[] dx = {0, 1, 0, -1};
	static int[] dy = {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());
    	
    	map = new int[N][M];
    	
    	for(int i=0; i<N; i++) {
    		st = new StringTokenizer(br.readLine(), " ");
    		for(int j=0; j<M; j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	// 회전시켜야하는 덩어리 수 만큼 반복
    	int nN = N;
    	int nM = M;
    	for(int i=0; i<Math.min(M, N)/2; i++) {
    		/*
    		 * i : 회전을 시작할 좌표
    		 * 2*N + 2*M - 4 : 처음엔 가장 겉 테두리의 갯수, 그 다음엔 각 변 길이가 2씩 줄도록 해서 넣어줌
    		 */
    		rotate(i, 2*nN + 2*nM - 4);
    		nN -= 2;
    		nM -= 2;
    	}
    	
    	print();
    }

    static void rotate(int start, int len) {
    	
    	// 나누기 연산을 사용하여 반복되는 반복을 최소화 해준다.
    	int cir = R % len;
    	
    	// 새롭게 구해낸 회전 횟수 만큼 회전시킴
    	for(int t=0; t<cir; t++) {
    		
    		int temp = map[start][start]; // 마지막에 넣을 값 미리 빼놓음
    		
    		int idx = 0; // 다음 값 탐색할 인덱스
    		
    		int x = start;
			int y = start;
			
    		while(idx < 4) {
    			
    			int nx = x + dx[idx];
    			int ny = y + dy[idx];
    			
    			if(nx >= start && ny >= start && nx < N-start && ny < M-start) {
    				map[x][y] = map[nx][ny];
    				x = nx;
    				y = ny;
    			} else {
    				idx++;
    			}
    		}
    		map[start+1][start] = temp;	// 마지막에 미리 빼놨던 값 넣엊둠
    	}
    	
    }
    
    static void print() {
    	for(int i=0; i<N; i++) {
    		for(int j=0; j<M; j++) {
    			System.out.print(map[i][j]+" ");
    		}
    		System.out.println();
    	}
    }
	
}

정리

• 회전 하는 횟수 R이 10^9 까지이기 때문에 그냥 돌리면 시간초과가 난다.
• 시간 복잡도를 먼저 생각하고 문제 풀이를 해야한다.