백준 배열 돌리기 2(16927)

배열 돌리기 2

1. 힌트

1) 덱을 사용해서 맨 앞에 있는 원소를 빼고 맨 뒤에 다시 넣는 식으로 돌리기 연산을 쉽게 구현할 수 있습니다.

2) 배열의 바깥쪽부터 돌면서 $min(N, M)$개의 덱에 넣어줍니다. 도는 시작 지점이 $(k,\ k)$라고 생각하면은 쉽게 반복할 수 있습니다.

3) 배열의 크기는 작은데 돌리는 횟수는 너무 큽니다. 덱의 크기가 $size$라고 할 때 $size$만큼 돌린 것은 돌리지 않은 것과 같으므로 우리는 $R\ mod\ size$만큼만 돌려도 된다는 것을 알 수 있습니다.

2. 접근

힌트 참조

3. 구현

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		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[][] S = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) S[i][j] = Integer.parseInt(st.nextToken());
		}
		ArrayList<Deque<Integer>> L = new ArrayList<>();
		for (int k = 0; k < Math.min(N, M) / 2; k++) {
			L.add(new LinkedList<>());
			for (int j = k; j < M - k; j++) L.get(k).offer(S[k][j]);
			for (int i = k + 1; i < N - k; i++) L.get(k).offer(S[i][M - k - 1]);
			for (int j = M - k - 2; j >= k; j--) L.get(k).offer(S[N - k - 1][j]);
			for (int i = N - k - 2; i > k; i--) L.get(k).offer(S[i][k]);
		}
		for (Deque<Integer> x : L)
			for (int i = 0; i < R % x.size(); i++)
				x.offer(x.poll());
		for (int k = 0; k < Math.min(N, M) / 2; k++) {
			for (int j = k; j < M - k; j++) S[k][j] = L.get(k).poll();
			for (int i = k + 1; i < N - k; i++) S[i][M - k - 1] = L.get(k).poll();
			for (int j = M - k - 2; j >= k; j--) S[N - k - 1][j] = L.get(k).poll();
			for (int i = N - k - 2; i > k; i--) S[i][k]= L.get(k).poll();
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) bw.append(S[i][j]).append(" ");
			bw.append("\n");
		}
		System.out.print(bw);
	}

}