[Python] 백준 14891번 톱니바퀴

골드5

 

.

---

구현

Python - Deque 

Deque는 양방향큐로 앞 뒤 양쪽에서 element 추가, 제거 가능

리스트 연산은 O(N)인데 Deque 사용시 O(1)

스택 / 큐 모두 활용 가능

 

rotate 함수를 통해 deque를 num만큼 회전 가능(양수면 오른쪽, 음수면 왼쪽)

from collections import deque

deq = deque()

# Add element to the start
deq.appendleft(10)

# Add element to the end
deq.append(0)

# Pop element from the start
deq.popleft()

# Pop element from the end
deq.pop()

# Contain 1, 2, 3, 4, 5 in deq
deq = deque([1, 2, 3, 4, 5])

deq.rotate(1)
print(deq)
# deque([5, 1, 2, 3, 4])

deq.rotate(-1)
print(deq)
# deque([1, 2, 3, 4, 5])

풀이

# 백준 14891번 톱니바퀴
from collections import deque

# deque, 양방향 큐
wheel = [deque(list(map(int,input().rstrip()))) for _ in range(4)]

# 왼쪽 톱니바퀴 체크
def left_check(num, dir):
    if num < 0:
        return
    if wheel[num][2] != wheel[num + 1][6]:
        left_check(num - 1, -dir) # 왼쪽 재귀호출하여 체크
        wheel[num].rotate(dir) # 왼쪽 톱니바퀴 회전(기준과 반대방향)

# 오른쪽 톱니바퀴 체크
def right_check(num, dir):
    if num > 3:
        return
    if wheel[num][6] != wheel[num - 1][2]:
        right_check(num + 1, -dir) # 오른쪽 재귀호출하여 체크
        wheel[num].rotate(dir) # 오른쪽 톱니바퀴 회전

k = int(input())
for _ in range(k):
    num, dir = map(int, input().split()) # 회전하는 톱니바퀴, 방향
    num = num - 1 # 인덱스
    left_check(num - 1, -dir) 
    right_check(num + 1, -dir)
    wheel[num].rotate(dir) # 현재 톱니바퀴 회전

result = 0
for i in range(4):
    result += (2 ** i) * wheel[i][0]
print(result)

---

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

14891번: 톱니바퀴