문제
문제
크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.
입력
첫째 줄에 배열의 크기 N M 수행해야 하는 회전의 수 R
둘째 줄부터 N개의 줄까지 배열 A의 원소 제공
출력
배열을 R번 회전 시킨 결과
풀이
시뮬레이션 같다. 다만 최적화를 좀 적용하면 좋지 않을까...
4x5일 때 가장 겉면은 14번 돌아가면 제자리, 안은 6번 돌아가면 제자리
그러니까 돌리긴 하는데 원상복귀되는 값을 구해서 나눗셈을 미리 하면 최적화를 할 수 있을 것 같아서 초기화 기준을 미리 구하고 돌렸다.
돌리는 건 다음과 같이 구현했다.
첫 번째 값(예를 들어 0,0)을 미리 저장해두고
(0, 0) - (0, 1) - (0, 2) - ... 이 칸을 왼쪽으로 한 칸씩 민다.
이후 (M-1, 0) - (M-2, 0) -... 아래로 한 칸씩 밀고, 오른쪽으로 한 칸씩 밀고 위로 한 칸씩 민 뒤 마지막에 첫 번째 값을 배치한다.
이 방법을 R%r[i] 나머지만큼만 진행한 뒤, 값을 출력한다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
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[][] arr = new int[N][M];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
// 초기화 기준 구하기
int[] r = new int[(Math.min(N, M))/2];
for(int ring = 0; ring < r.length; ring++) {
int height = N - (2*ring);
int width = M - (2*ring);
r[ring] = 2*height + 2*width - 4;
}
for(int i=0; i<r.length; i++) {
int border = i;
for(int rR = 0; rR<R%r[i]; rR++) {
// 첫 번째 값
int temp = arr[border][border];
// 왼쪽으로
for(int k = border; k < M-1-border; k++) {
arr[border][k] = arr[border][k+1];
}
// 아래로
for(int k = border; k < N-1-border; k++) {
arr[k][M-1-border] = arr[k+1][M-1-border];
}
// 오른쪽으로
for(int k = M-1-border; k > border; k--) {
arr[N-1-border][k] = arr[N-1-border][k-1];
}
// 위로
for(int k = N-1-border; k > border+1; k--) {
arr[k][border] = arr[k-1][border];
}
// 마지막에 첫 번째 값 배치
arr[border+1][border] = temp;
}
}
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
bw.write(arr[i][j] + " ");
}
bw.write("\n");
}
bw.flush();
bw.close();
br.close();
}
}문제를 풀며
생각보다 미는 걸 구현하는 데에 시간을 많이 쏟았다... 돌리는 부분만 따로 메소드로 뺐어도 좋았을 것 같다.
그리고 찾아봤더니 temp 변수 대신 배열 전체를 shift 하는 방식도 존재하는 것 같다. List에 제일 겉 부분 링을 쭈욱 넣어두고 민다고 생각하는 것이다. 일차원 순환 배열을 밀어서 표현하는 방식이다. 현재 코드를 쓸 때는 헷갈려서 이래저래 숫자도 변수도 바꾸는 일이 많았는데, 이 방법을 쓰면 덜 헷갈리고 좋을 것 같다. 참고한 블로그의 링크 :
+ O(n^2)로 푸는 법 : 각 배열의 위치별로 수식을 적용해서