톱니바퀴 ( 14891 번 )

14891번: 톱니바퀴

 

---

🧠 알고리즘

• 시뮬레이션 (Simulation) + 덱(Deque) 회전 구현

 

✔️ 동작 방식

문제 핵심 아이디어
4개의 톱니바퀴가 각각 8개의 자석극(N/S)을 가지고 있으며,
하나를 회전시키면 인접한 톱니의 맞닿은 극이 다를 경우 반대 방향으로 회전한다.

이를 시뮬레이션으로 구현하여, 모든 회전 명령 이후 4개의 톱니 상태를 계산하고
각 톱니의 12시 방향이 S극(‘1’)이면 점수를 더하는 방식이다.

 

주요 로직 요약

1. 입력 처리
   • 4개의 톱니바퀴를 deque 형태로 입력받음 (시계방향 회전 효율적)
   • 회전 명령 수 play_count 입력
2. 회전 전파 계산 (_cr_play)
   • 기준 톱니(t_num)가 시계/반시계 회전할 때,
     좌측·우측 톱니가 맞닿는 극(2번, 6번 인덱스)을 비교하여
     극이 다르면 반대 방향으로 회전하도록 설정
   • 연결된 톱니들은 연쇄적으로 방향이 결정됨 (왼쪽, 오른쪽 각각 전파)
3. 톱니 회전 수행 (_main)
   • _cr_play로 계산된 회전 방향 배열(now_play_type)을 이용해
     실제 덱(deque) 회전 수행
     • 시계(1): appendleft(pop())
     • 반시계(-1): append(popleft())
4. 결과 계산
   • 모든 명령 수행 후, 각 톱니의 12시 방향이 ‘1’(S극)이면
     2^톱니번호 만큼 점수 합산

---

 

🧾 코드

import sys
from collections import deque

def _cr_play(t_num, play_type):
    answer = [0] * 4
    answer[t_num] = play_type

    # 왼쪽 확인
    for next_t_num in range(t_num - 1, -1, -1):
        if t_list[next_t_num][2] != t_list[next_t_num + 1][6]:
            answer[next_t_num] = (answer[next_t_num + 1] * -1)
        else:
            break

    # 오른쪽 확인
    for next_t_num in range(t_num + 1, 4, 1):
        if t_list[next_t_num][6] != t_list[next_t_num - 1][2]:
            answer[next_t_num] = (answer[next_t_num - 1] * -1)
        else:
            break

    return answer


def _main(play_count):
    answer = 0
    
    for _ in range(play_count):
        t_num, play_type = map(int, sys.stdin.readline().rstrip().split())
        t_num -= 1

        now_play_type = _cr_play(t_num, play_type)
        for idx in range(4):
            if now_play_type[idx] == -1: # 반시계
                t_list[idx].append(t_list[idx].popleft())
            elif now_play_type[idx] == 1: # 시계
                t_list[idx].appendleft(t_list[idx].pop())

    for idx in range(4):
        if t_list[idx][0] == '1':
            answer += (1 << idx)

    return answer


a = deque(sys.stdin.readline().rstrip())
b = deque(sys.stdin.readline().rstrip())
c = deque(sys.stdin.readline().rstrip())
d = deque(sys.stdin.readline().rstrip())
play_count = int(sys.stdin.readline().rstrip())

t_list = [a, b, c, d]
print(_main(play_count))

---

 

⏱️ 시간 복잡도

for _ in range(play_count) : 시행 횟수만큼 톱니바퀴 시뮬레이션 ( 선형 시간 )

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )