문제 링크

https://www.acmicpc.net/problem/17822

문제 설명

• 원판이 크기 순으로 쌓아져 있다
• 인접 조건
  • 같은 원판에서 붙어있음
  • 다른 원판의 같은 인덱스
• 인접하고 같은 숫자가 있으면 삭제
• 하나도 없으면 평균을 구해서 +-1
• 마지막에 남아있는 숫자의 합 출력

풀이

• 회전
  • 리스트 슬라이싱
• 인접한지 체크
  • 두 번 순회

후기

• deque를 쓰면 회전이 빠르고 인덱싱이 느리다
• list를 쓰면 회전이 느리고 인덱싱이 빠르다
• 둘 다 해결하려고 원판별로 start 인덱스를 리스트로 저장해보려 했는데 실패
  • 인접한 인덱스를 찾는건 괜찮은데 삭제하는게 어려웠다
• 그래서 list와 deque중에서 list를 선택했다
  • deque는 NxM 개의 노드를 모두 인덱싱(O(M))해야 하고
  • list는 N개의 원판을 회전(O(N))해야 하기 때문이다

코드

def rotate(x, to_left, k):
    for i in range(1, n+1):
        if i % x != 0:
            continue
        front = board[i][m-k:]
        back = board[i][:m-k]
        if to_left:
            front = board[i][k:]
            back = board[i][:k]
        board[i] = front + back


def change():
    to_delete = find()
    if to_delete:
        for i, j in to_delete:
            board[i][j] = float('inf')
    else:
        summ, count = 0, 0
        for i in range(1, n+1):
            for j in range(m):
                if board[i][j] == float('inf'):
                    continue
                summ += board[i][j]
                count += 1
        if count == 0:
            return
        for i in range(1, n+1):
            for j in range(m):
                if summ / count > board[i][j]:
                    board[i][j] += 1
                elif summ / count < board[i][j]:
                    board[i][j] -= 1


def find():
    to_delete = set()
    # check rows
    for i in range(1, n+1):
        for j in range(m):
            if board[i][j] == float('inf') or board[i][(j+1)%m] == float('inf'):
                continue
            if board[i][j] == board[i][(j+1)%m]:
                to_delete.add((i, j))
                to_delete.add((i, (j+1)%m))
    # check cols
    for j in range(m):
        for i in range(1, n):
            if board[i][j] == float('inf') or board[i+1][j] == float('inf'):
                continue
            if board[i][j] == board[i+1][j]:
                to_delete.add((i, j))
                to_delete.add((i+1, j))
    return to_delete


def get_sum():
    summ = 0
    for i in range(1, n+1):
        for j in range(m):
            if board[i][j] == float('inf'):
                continue
            summ += board[i][j]
    return summ


import sys
read = sys.stdin.readline
n, m, t = map(int, read().split())
board = [[] for _ in range(n+1)]
for i in range(1, n+1):
    board[i] = list(map(int, read().split()))
commands = [list(map(int, read().split())) for _ in range(t)]


for x, d, k in commands:
    rotate(x, d, k)
    change()
print(get_sum())