원판을 오른쪽 왼쪽 회전시키면 숫자의 위치가 회전한다는 걸 보고 파이썬의 Deque 가 생각났다.
BFS를 구현할때 자주 쓰던 자료구조인데 리스트의 맨 처음과 끝에 자료의 추가 삭제가 O(1) 에 가능해서 적합했다.자바에서는 Deque 대신 LinkedList를 이용해 구현했는데 풀고 생각해보니 LinkedList의 경우 인덱스 접근에 O(n)이 걸린다는 사실이 생각났다.
풀이에서 꽤 자주 인덱스 접근이 들어가기에 시간초과를 걱정했지만 LinkedList 의 크기가 최대 50이어서 시간초과는 안났던거 같다.수정
찾아보니 python 의 deque 도 인덱스 접근은 O(1)이 아니었다.
제출코드
파이썬
import sys
input = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(5000)
def rotate(num, k, dir):
for _ in range(k):
if dir == 0: # 시계방향
a = boards[num].pop()
boards[num].appendleft(a)
else: # 반시계
a = boards[num].popleft()
boards[num].append(a)
def edit_number(num):
flag = 1
for i in range(M):
if boards[num][i] != 0:
target = boards[num][i]
boards[num][i] = 0
if recur(num, i, target) != True:
boards[num][i] = target
else:
flag = 0
return flag
def recur(num, idx, target):
flag = False
if num < N and boards[num+1][idx] == target: # 위쪽 원으로 이동
boards[num+1][idx] = 0
flag = True
recur(num+1, idx, target)
if num > 1 and boards[num-1][idx] == target: # 아래이동
boards[num-1][idx] = 0
flag = True
recur(num-1, idx, target)
l, r = reIdx(idx)
if boards[num][l] == target:
boards[num][l] = 0
flag = True
recur(num, l, target)
if boards[num][r] == target:
boards[num][r] = 0
flag = True
recur(num, r, target)
return flag
def fail_edit():
v = 0
cnt = 0
for i in range(1, N+1):
for j in range(M):
if boards[i][j] != 0:
cnt += 1
v += boards[i][j]
if cnt == 0:
return
v /= cnt
for num in range(1, N+1):
for i in range(M):
if boards[num][i] != 0:
if boards[num][i] > v:
boards[num][i] -= 1
elif boards[num][i] < v:
boards[num][i] += 1
def reIdx(idx):
if idx == 0:
return M-1 , 1
return idx-1, (idx+1)%M
N, M, T = map(int, input().split())
boards = [0 for _ in range(N+1)]
for i in range(1, N+1):
boards[i] = deque(list(map(int, input().split())))
for _ in range(T):
# x의 배수 원판을 d방향으로 k번 회전
x, d, k = map(int, input().split())
for num in range(x, N+1, x):
rotate(num, k, d)
isEdit = 1
for num in range(1, N+1):
isEdit *= edit_number(num)
if isEdit == 1: # 숫자가 한번이라도 바뀌었다면 isEdit == 0 이 될것
fail_edit()
ans = 0
for i in range(1, N+1):
ans += sum(boards[i])
print(ans)자바
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
static int N;
static int M;
static int T;
static int[][] command;
static LinkedList<Integer>[] board;
public static void main(String[] args) throws IOException {
inputMethod();
for (int tc = 0; tc < T; tc++) {
int x = command[tc][0];
int d = command[tc][1];
int k = command[tc][2];
for (int num = x; num < N+1; num += x) {
rotate(num, k, d);
}
int isEdit = 1;
for (int num = 1; num < N+1; num++) {
isEdit *= edit_number(num);
}
if (isEdit == 1) {
failEdit();
}
}
int ans = 0;
for (int i = 1; i < N+1; i++) {
for (int j = 0; j < M; j++) {
ans += board[i].get(j);
}
}
System.out.println(ans);
}
public static void inputMethod() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
T = Integer.parseInt(st.nextToken());
board = new LinkedList[N+1];
for (int i = 1; i < N+1; i++) {
LinkedList<Integer> LL = new LinkedList<>();
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
LL.add(Integer.parseInt(st.nextToken()));
}
board[i] = LL;
}
command = new int[T][3];
for (int i = 0; i < T; i++) {
st = new StringTokenizer(br.readLine());
command[i][0] = Integer.parseInt(st.nextToken());
command[i][1] = Integer.parseInt(st.nextToken());
command[i][2] = Integer.parseInt(st.nextToken());
}
}
public static void rotate(int num, int k, int dir) {
for (int i = 0; i < k; i++) {
if (dir == 0) {
int a = board[num].pollLast();
board[num].addFirst(a);
} else {
int a = board[num].pollFirst();
board[num].addLast(a);
}
}
}
public static int edit_number(int num) {
int flag = 1;
for (int i = 0; i < M; i++) {
int target = board[num].get(i);
if (target != 0) {
board[num].set(i, 0);
if (recur(num, i, target) != true) {
board[num].set(i, target);
} else {
flag = 0;
}
}
}
return flag;
}
public static boolean recur(int num, int idx, int target) {
boolean flag = false;
if (num < N && board[num+1].get(idx) == target) {
board[num+1].set(idx, 0);
flag = true;
recur(num+1, idx, target);
}
if (num > 1 && board[num-1].get(idx) == target) {
board[num-1].set(idx, 0);
flag = true;
recur(num-1, idx, target);
}
int r = (idx+1) % M;
int l = idx - 1;
if (l == -1) {
l = M-1;
}
if (board[num].get(r) == target) {
board[num].set(r, 0);
flag = true;
recur(num, r, target);
}
if (board[num].get(l) == target) {
board[num].set(l, 0);
flag = true;
recur(num, l, target);
}
return flag;
}
public static void failEdit() {
double v = 0;
double cnt = 0;
for (int i = 1; i < N+1; i++) {
for (int j = 0; j < M; j++) {
int a = board[i].get(j);
if (a != 0) {
v += a;
cnt += 1;
}
}
}
if (cnt == 0) {
return ;
}
v /= cnt;
for (int num = 1; num < N+1; num++) {
for (int i = 0; i < M; i++) {
int a = board[num].get(i);
if (a > v) {
board[num].set(i, a-1);
} else if ( 0 < a && a < v) {
board[num].set(i, a+1);
}
}
}
}
}접근방법
구현 문제 답게 접근 방법은 간단하다.
회전시키고 DFS 방식으로 연결된 숫자를 처리한다. 연결된 숫자가 없다면 다른 처리를 진행한다.
뚝딱뚝딱