[Java] Baekjoon16926: 배열 돌리기 1
배열 돌리기 1
| 1 초 | 512 MB | 6571 | 3266 | 2195 | 49.293% |
문제
크기가 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 ≤ 1,000
- min(N, M) mod 2 = 0
- 1 ≤ Aij ≤ 108
풀이
배열의 껍질마다 경로가 다르기 때문에 몇 개의 껍질이 있는지 그리고 각각의 껍질의 왕복 거리는 어떻게 되는지 구합니다.
껍질 개수
2x2 행렬에서 껍질의 개수는 1개입니다.
2x4 행렬에서 껍질의 개수는 1개입니다.
4x2 도 마찬가지입니다.
껍질의 개수는 M과 N 중 최소값을 나누기 2한 값입니다.
4x6이라면? 껍질의 개수는 2개인 것입니다.
껍질의 원소들을 구분하기
가장 최외각 껍질에 있는 원소들은 모두 배열의 경계선에 있습니다.
<첫번째 껍질 원소들의 위치>
- 행이 0이거나 N-1인 모든 원소
- 열이 0이거나 M-1인 모든 원소
<두번째 껍질 원소들의 위치>
- 행이 1이거나 N-2인 모든 원소
- 열이 1이거나 M-2인 모든 원소
껍질마다 왕복거리 (원소의 개수) 구하기
최외곽 껍질은 : 2(N+M)-4 개
다음 껍질은 : 2(N-2+M-2)-4 = 2(N+M)-12개
8개씩 줄어듭니다.
회전수 R이 주어졌을 때 껍질마다의 알짜 회전수
왕복한다면 자기 위치로 돌아옵니다.
R을 껍질의 원소 개수로 나눈 나머지가 알짜 회전수입니다.
원소들을 회전 시키기: K번째 껍질에 대해서
전체 껍질의 수 = 입력받은 N과 M 중 최소값 ÷ 2
껍질 원소들의 위치
- 행이 K-1 나 N-K번 인덱스일 때
- 열이 K-1 나 N-K번 인덱스일 때
- 모서리 = 위 두 조건을 모두 만족하는 곳
모서리에 도달했을 때 회전 방향은 바뀜
어떻게 이동?
현재 위치에 따라서 현재 방향을 배분: 상 하 좌 우
먼저 껍질 맨 위 원소들은 왼쪽 이동 방향
껍질 맨 왼쪽은 아래
껍질 맨 아래는 오른쪽
껍질 맨 오른쪽은 위 로 이동하려는 경향이 있다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int R = Integer.parseInt(st.nextToken());
int[][] matrix = new int[N][M];
int[][] direction = new int[N][M]; //상:1 하:2 좌:3 우:4
int[][] count = new int[N][M];
int[][] answer = new int[N][M];
int shell = Math.min(N, M)/2;
int element = 2*(M+N)-4; //원소 개수
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
matrix[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int s=0; s<shell; s++) {
int start = s;
int row_last = N-1-s;
int col_last = M-1-s;
int net_R = R%element;
for(int i=start; i<=col_last; i++) {
direction[start][i] = 3; // 첫째줄
direction[row_last][i] = 4; //마지막 줄
count[start][i] = net_R;
count[row_last][i] = net_R;
}
for(int j=start; j<=row_last; j++) {
direction[j][start] = 2; //첫째열
direction[j][col_last] = 1; //마지막 열
count[j][start] = net_R;
count[j][col_last] = net_R;
}
direction[start][start] = 2; //왼쪽 위 모서리
direction[row_last][start] = 4; //왼쪽 아래 모서리
direction[row_last][col_last] = 1; //오른쪽 아래 모서리
direction[start][col_last] = 3; //오른쪽 위 모서리
element -= 8;
}
for(int i=0; i<N;i++) {
for(int j=0; j<M;j++) {
int row=i;
int col=j;
while(count[i][j]-->0) {
switch(direction[row][col]) {
case 1: row--; break;
case 2: row++; break;
case 3: col--; break;
case 4: col++; break;
}
}
answer[row][col] = matrix[i][j];
}
}
for(int i=0; i<N;i++) {
for(int j=0; j<M;j++) {
System.out.print(answer[i][j]+" ");
}
System.out.println();
}
}
}