[BOJ] 2932 표회전 - java

리뷰

공간복잡도를 고려하지 못해 틀린 문제

 

 

제한

- 시간: 1초, 메모리: 128MB

- 표의 크기 N: 2 ~ 10,000

- 이동시키려는 숫자의 수 K: 1 ~ 1,000

- O(N^2), O(K*N)까지 가능하며 완전탐색의 경우는 아닐 가능성이 크다는 결론을 내릴 수 있다.

- 이동시키려는 숫자당 O(N)을 넘지않는지 주의하자.

 

 

유형

Goal: 숫자 K개를 이동시키는데 필요한 회전의 수

표가 수행할 수 있는 행 회전, 열 회전 연산이 있으며 문제에서 주어진 방식 그대로 구현하는 시뮬레이션 문제임을 파악할 수 있다.

 

 

Worst Case

N = 10,000, K = 1,000

공간복잡도: 표를 직접 구현하면 N^2 * 4byte / 1024 / 1024 = 약 381MB로 공간복잡도가 터지게 된다. 표를 직접 구현하여 접근하는 문제가 아님을 파악해야한다.

 

시간복잡도: 타겟 T가 (R,C)로 이동하는데 배열 한 칸씩 이동하는 경우 2만번 소요된다. K회를 해야하므로 O(K*2만)으로 가능하다.

 

 

설계

1. 표를 직접 구현하는 방식은 안된다.

문제의 예시를 직접 그려보면, 결국 타겟 T들의 위치만 관리하면 된다.

 

2. 타겟 T들의 위치 관리하기

1. 현재 타겟 T의 (R,C)로의 col 이동수를 구한다. (행회전)
   col 이동수 = ( N + 목표col - 현재col ) % N
2. 현재 타겟 T의 (R,C)로의 row 이동수를 구한다. (열회전)
   row 이동수 = ( N + 목표row - 현재row ) % N
3. 현재 타겟 T와 같은 행에 있는 혹은 같은 숫자인 타겟들의 col 위치를 갱신한다.
   ∵ 행회전 시, 같은 행에 있는 타겟들의 위치가 바뀜
4. 현재 타겟 T가 이동한 열에 있는 혹은 같은 숫자인 타겟들의 row 위치를 갱신한다.
   ∵ 열회전 시, 이동한 열과 같은 열에 있는 타겟들의 위치가 바뀜

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	private static int R, C, N, K;
	private static Target[] targets;

	public static void main(String[] args) throws IOException {
		input();
		pro();
	}

	private static void pro() {
		StringBuilder result = new StringBuilder();
		for (int idx = 0; idx < targets.length; idx++) {
			Target target = targets[idx];
			// 타겟T -> (R,C)이동의 열 이동수를 구한다.
			int moveColCount = getMoveColCount(target);
			// 타겟T -> (R,C)이동의 행 이동수를 구한다.
			int moveRowCount = getMoveRowCount(target);
			// 다음 타켓들의 위치를 갱신한다.
			updatePosition(target, idx + 1, moveColCount, moveRowCount);

			result.append(moveColCount + moveRowCount).append("\n");
		}
		System.out.println(result.toString());
	}

	private static int getMoveColCount(Target target) {
		int moveColCount = 0;
		int destCol = target.destCol;
		moveColCount = (N + destCol - target.col) % N;
		return moveColCount;
	}

	private static int getMoveRowCount(Target target) {
		int moveRowCount = 0;
		int destRow = target.destRow;
		moveRowCount = (N + destRow - target.row) % N;
		return moveRowCount;
	}

	private static void updatePosition(Target cur, int idx, int moveColCount, int moveRowCount) {
		for (int i = idx; i < targets.length; i++) {
			Target next = targets[i];
			// 같은 번호이면 R, C로 갱신한다.
			if (cur.num == next.num) {
				next.row = cur.destRow;
				next.col = cur.destCol;
				continue;
			}
			// 같은 행이면 col을 갱신한다.
			if (cur.row == next.row) {
				int temp = (next.col + moveColCount) % N;
				if (temp == 0) {
					temp = N;
				}
				next.col = temp;
				continue;
			}
			// destCol로 이동했을 때와 같은 열이면 row를 갱신한다.
			if (cur.destCol == next.col) {
				int temp = (next.row + moveRowCount) % N;
				if (temp == 0) {
					temp = N;
				}
				next.row = temp;
				continue;
			}
		}
	}

	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		targets = new Target[K];
		for (int idx = 0; idx < K; idx++) {
			st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken());
			int destRow = Integer.parseInt(st.nextToken());
			int destCol = Integer.parseInt(st.nextToken());

			targets[idx] = new Target(num, (num - 1) / N + 1, (num - 1) % N + 1, destRow, destCol);
		}
	}
}

class Target {
	int num;
	int row;
	int col;
	int destRow;
	int destCol;

	public Target(int num, int row, int col, int destRow, int destCol) {
		this.num = num;
		this.row = row;
		this.col = col;
		this.destRow = destRow;
		this.destCol = destCol;
	}
}