[JAVA] 백준 16927 배열돌리기 2

배열 돌리기 2 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

2579

836

668

34.846%

문제

크기가 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

---

풀이과정 :

이건 배열이 n*m 일때  둘중작은값을 N 이라고하면 N/2 개의 테두리를 따로 생각해야되는 문제입니다.

회전수 R 을 실제로 다돌려버린다면 시간초과가 나버리기 때문에 실제 회전수를 구해야되는데

실제회전수는 R%N번째 테두리의 원소 갯수 입니다

제가 생각한 방식은 실제값을 가지고있는 Queue A와 인덱스를 가지고있는 Queue B을 테두리를 돌면서 각각 동시에 넣어주고 . Queue A 의 값을  R%A.size() 만큼 A.add(A,pop()) 을 통해 앞의 원소를 뒤로 보내고

A.pop() 을 B.pop() 의 인덱스에 넣어주는 방식을 사용했습니다

 

> 실제 예시

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

첫 for문       queue A > 1, 2,3, 4,8,12,16,15,14,13,9,5 >>실제값

                  queue B > 1, 2,3, 4,8,12,16,15,14,13,9,5 >>인덱스 번호 

만약 회전수가 R 이면  ㅠint rotate =R%A.size();

해서 실제 회전수를 구하고

회전수 만큼 A

for(int i =0; i<rotate ;i++) {

                                                     A.add(A.poll());

 

}

위 과정을 거치면 

rotate 가 만약 2일때 >

queue A >3, 4,8,12,16,15,14,13,9,5,1, 2 >>변경된 큐

queue B > 1, 2,3, 4,8,12,16,15,14,13,9,5 >>인덱스 번호 

A.pop() 을 B.pop()  자리에 넣어주게 되면 다음과 같다

3 4 8 12

2 6 7 16

1 10 11 15

5  9  13  14

 

 

위와같은 과정을 N/2 만큼 처리해 줍니다

 

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

public class bj_16926 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
		StringBuilder sb = new StringBuilder();
		st = new StringTokenizer(bf.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int R = Integer.parseInt(st.nextToken());
		int [][] map= new int[N][M];
		int [][] answer = new int[N][M];
		
		for(int i =0; i<N;i++) {  // 배열로 받아옴
			st = new StringTokenizer(bf.readLine());
			for(int j =0; j<M;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				
			}						
		}
		Queue<Integer> value_queue = new LinkedList<>();
		Queue<Integer[]> idx_queue = new LinkedList<>();
		int start_i= 0;
		int end_i = N;
		int start_j= 0;
		int end_j = M;
		
		int size= Math.min(N,M)/2;
		for(int T =0;  T<size;T++) {
		
			int i_i =start_i;
			int j_j =start_j;
			while(true) {
				value_queue.add(map[i_i][j_j]);
				idx_queue.add(new Integer[] {i_i , j_j});
				if(j_j+1<end_j) { // 오른쪽으로 이동
					j_j =j_j+1;
					continue;
				}
				if(i_i+1<end_i) { // 아래쪽으로 이동 
					i_i= i_i+1;
					continue;
					
				}
				break;
			
			}
			while(true) {
				
				if(start_j<=j_j-1) { // 왼쪽으로 이동 
					j_j =j_j-1;
					value_queue.add(map[i_i][j_j]);
					idx_queue.add(new Integer[] {i_i , j_j});
					continue;
					
				}
				if(i_i-1>start_i) { // 위로
					i_i= i_i-1;
					value_queue.add(map[i_i][j_j]);
					idx_queue.add(new Integer[] {i_i , j_j});
					continue;
					
				}
				break;
			
			}
			
			start_i++;
			end_i--;
			start_j++;
			end_j--;
			
			int rotate =R%value_queue.size();
			
			for(int i =0; i<rotate ;i++) {
				value_queue.add(value_queue.poll());
			}
			int len = value_queue.size();
			for(int i =0 ; i <len;i++) {
				Integer [] answer_idx  = idx_queue.poll();
				answer[answer_idx[0]][answer_idx[1]] = value_queue.poll();
				
			}
			
			
			
		
			
			
		}
		
		for(int i = 0; i<N ;i++) {
			for (int j=0; j<M;j++) {
				if(j!=M-1) {
					sb.append(answer[i][j]+" ");
				}
				else {
					sb.append(answer[i][j]);
					
				}
			}
			sb.append("\n");
		}
		System.out.println(sb);
	

	}
}