출처
알고리즘 분류
- 구현
- 시뮬레이션
문제
풀이
먼저, 톱니바퀴의 상태를 효율적으로 업데이트하기 위해서 deque 자료구조를 사용하였습니다. 초기 상태가 톱니바퀴가 01000000인 톱니바퀴가 있다고 가정을 했을 때, 해당 톱니바퀴가 시계방향으로 회전하는 경우에는 01000000 -> 00100000, 반시계방향으로 회전하는 경우에는 01000000 -> 10000000 로 상태가 바뀌게 됩니다. 즉, deque 자료구조를 통한 회전 연산을 요약하면 다음과 같습니다.
- 시계방향으로 회전시에는 pop 연산을 통해 삭제한 데이터를 appendleft 연산을 통해 deque의 맨 앞에 추가합니다.
- 반시계방향으로 회전시에는 popleft 연산을 통해 추출한 데이터를 append 연산을 통해 deque의 맨 뒤에 추가합니다.
따라서, 해당 연산을 함수로 다음과 같이 구현할 수 있습니다.
def rotation(n, d):
if d == 1:
gear_list[n].appendleft(gear_list[n].pop())
else:
gear_list[n].append(gear_list[n].popleft())다음은 회전시킬 톱니바퀴의 번호와 방향을 입력받은 뒤, 톱니바퀴의 상태를 바탕으로 어떤 톱니바퀴를 어떤 방향으로 추가적으로 회전시켜야 하는지를 구해야 합니다. 입력받은 톱니바퀴 번호를 기준으로 왼쪽, 오른쪽 방향으로 서로 맞닿은 톱니의 극이 다른 경우를 순차적으로 탐색합니다.
회전시킬 톱니바퀴의 번호를 cur이라고 했을 때, 해당 톱니바퀴의 왼쪽과 오른쪽의 번호는 cur - 1, cur + 1이 될 것입니다. 현재 톱니바퀴의 6번 인덱스와 왼쪽 톱니바퀴의 2번 인덱스가 일치하지 않는 경우, 추가적으로 회전시켜야 하는 톱니바퀴의 번호와 방향을 저장하는 rotate_idx 배열에 왼쪽 톱니바퀴의 번호와 방향을 저장합니다. 맞닿은 극이 다른 경우에는 회전한 톱니바퀴의 반대 방향으로 회전시켜야 하므로, 방향에 -1을 반복적으로 곱하여 해당 로직을 구현하였습니다. cur과 left값을 업데이트하면서 왼쪽 톱니바퀴가 존재하지 않는 경우 반복문을 종료합니다.
while left >= 0:
if gear_list[left][2] != gear_list[cur][6]:
rotate_idx.append((left, tmp_dir_1 * -1))
cur = left
left -= 1
tmp_dir_1 *= -1
else:
break오른쪽 톱니바퀴를 탐색하는 로직도 유사합니다. 이 때 주의할 점은, 탐색하기 전에 cur을 입력받은 톱니바퀴의 번호로 다시 초기화시켜야 한다는 점입니다. 현재 톱니바퀴의 2번 인덱스와 오른쪽 톱니바퀴의 6번 인덱스가 일치하지 않는 경우, 오른쪽 톱니바퀴의 번호와 방향을 저장합니다. cur과 right값을 업데이트하면서 오른쪽 톱니바퀴가 존재하지 않는 경우 반복문을 종료합니다.
cur = gear_num - 1
while right <= 3:
if gear_list[cur][2] != gear_list[right][6]:
rotate_idx.append((right, tmp_dir_2 * -1))
cur = right
right += 1
tmp_dir_2 *= -1
else:
break탐색이 모두 끝났으면, rotate_idx 배열에는 추가적으로 회전시켜야 하는 모든 톱니바퀴의 번호와 방향이 튜플 형태로 저장됩니다. 위에서 정의한 rotation 함수를 통해 추가적으로 회전시켜야 할 톱니바퀴의 상태와 입력받은 톱니바퀴의 상태까지 업데이트합니다.
for idx, dir in rotate_idx:
rotation(idx, dir)
rotation(gear_num - 1, direction)모든 톱니바퀴의 상태가 업데이트되었으면, 각 톱니바퀴의 12시 방향(0번 인덱스)이 1인 경우 조건에 맞게 점수를 추가합니다.
answer = 0
for i in range(4):
if gear_list[i][0] == 1:
answer += 2 ** i전체 코드는 아래와 같습니다.
from collections import deque
def rotation(n, d):
if d == 1:
gear_list[n].appendleft(gear_list[n].pop())
else:
gear_list[n].append(gear_list[n].popleft())
gear_list = []
for _ in range(4):
gear_list.append(deque(list(map(int, input()))))
K = int(input())
for _ in range(K):
gear_num, direction = map(int, input().split())
cur = gear_num - 1
left, right = cur - 1, cur + 1
rotate_idx = []
tmp_dir_1 = direction
tmp_dir_2 = direction
while left >= 0:
if gear_list[left][2] != gear_list[cur][6]:
rotate_idx.append((left, tmp_dir_1 * -1))
cur = left
left -= 1
tmp_dir_1 *= -1
else:
break
cur = gear_num - 1
while right <= 3:
if gear_list[cur][2] != gear_list[right][6]:
rotate_idx.append((right, tmp_dir_2 * -1))
cur = right
right += 1
tmp_dir_2 *= -1
else:
break
for idx, dir in rotate_idx:
rotation(idx, dir)
rotation(gear_num - 1, direction)
answer = 0
for i in range(4):
if gear_list[i][0] == 1:
answer += 2 ** i
print(answer)시간 복잡도
deque의 append, appendleft, pop, popleft 연산은 모두 에 수행할 수 있으므로, 시간복잡도는 쿼리의 개수 K에 비례하여 선형으로 증가합니다.
실행 결과
