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

21546 단어 알고리즘G5백준G5

문제 바로가기

나의 풀이

구현 문제인 만큼 풀이가 많이 복잡했다. 풀고나서 다른 사람들의 풀이를 봤는데 나만큼이나 복잡하게 풀어낸듯 하다.

문제의 요지는 한칸씩 돌리면 시간 초과가 나기 때문에 r 만큼 한번에 돌려줘야 한다.

나는 그림을 그려가며 n, m이 어떻게 주어지든 항상 한 껍질의 가장 왼쪽 위는 (index, index) 라는 것을 알아냈다.

그래서 왼쪽 위를 시작으로 같은 껍질에 있는 원소들을 순회하며 list에 담아두고, 다시 한바퀴를 그대로 돌면서 기존의 list index + 회전 횟수를 인덱스로 가지는 list 값을 arr에 담아줬다.

또한 boolean[][] visited를 통해 이미 회전한 껍질은 방문 표시를 해놓음으로써 (index, index)가 이미 방문한 경우 모든 껍질의 회전이 끝났다는 것을 뜻하게 된다.


나의 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

class Main {

	static int[][] arr;
	static boolean[][] visited;

	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());

		arr = new int[n][m];
		visited = new boolean[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 index = 0;
		while (!visited[index][index]) {
			rotate(index, n - index, m - index, r);
			index++;
		}

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				sb.append(arr[i][j]).append(" ");
			}
			sb.append("\n");
		}

		System.out.println(sb);
	}

	private static void rotate(int index, int row, int col, int count) {
		List<Integer> list = new ArrayList<>();
		int x = index;
		int y = index;
		while (y < col - 1) {
			list.add(arr[x][y++]);
		}
		while (x < row - 1) {
			list.add(arr[x++][y]);
		}
		while (y > index) {
			list.add(arr[x][y--]);
		}
		while (x > index) {
			list.add(arr[x--][y]);
		}
		while (y < col - 1) {
			visited[x][y] = true;
			arr[x][y++] = list.get(count++ % list.size());
		}
		while (x < row - 1) {
			visited[x][y] = true;
			arr[x++][y] = list.get(count++ % list.size());
		}
		while (y > index) {
			visited[x][y] = true;
			arr[x][y--] = list.get(count++ % list.size());
		}
		while (x > index) {
			visited[x][y] = true;
			arr[x--][y] = list.get(count++ % list.size());
		}
	}
}

좋은 웹페이지 즐겨찾기