BOJ 14891. 톱니바퀴

14891번: 톱니바퀴 (acmicpc.net)

14891번: 톱니바퀴

이번 문제의 경우 구현 자체는 그렇게 어렵진 않았으나 인덱스 위치가 많이 헷갈렸던 문제다.

 

톱니바퀴 네개가 주어지는데, 가장 왼쪽이 1번이고 가장 오른쪽이 4번이다.

입력으로는 톱니바퀴의 극성을 나타내는 배열이 주어진 뒤, 몇 번째 바퀴를 어느 방향으로 돌릴 건지가 주어진다.

 

여기서 주의할 점은 톱니바퀴의 극성을 나타내는 배열은 01011100 이런식으로 주어지는데

12시 방향부터 시계방향으로 주어지므로 인덱싱 할 때 알아두어야 한다.

 

풀이

나는 이 문제를 보자마자 덱을 떠올렸다.

본래 큐나 덱은 중간의 원소에 접근할 수 없는 것이 원칙이나

파이썬의 덱은 접근할 수 있기 때문이다.

 

물론 다른 언어에서 중간 원소에 접근할 수 없는 덱을 이용하면, 따로 극성 정보 배열을 두어서

덱의 원소를 [극성정보, 배열에서의 위치]로 설정한 뒤 별도의 인덱싱 과정을 거치면 될 것 같다.

 

덱을 이용하면 원소의 삽입과 제거를 O(1)에 할 수 있으므로 획기적으로 시간을 줄이고, 직관적이라 오류도 적다.

반시계로 돌리는 경우 popleft 후 append를 해주면 되고

시계방향으로 돌리는 경우 pop 후 appendleft를 해주면 된다.

 

 이후 연쇄반응이 문제인데, 한번 돌리고 난 뒤 그 옆에 있는 톱니를 돌리게 되면

이미 이전에 돌린 톱니바퀴를 한번 더 돌리는 경우가 발생할수도 있기 때문이다.

따라서 연쇄반응을 코딩할 때는 이전에 돌린 톱니바퀴는 빼고 연쇄시켜야 한다.

 

또한 가장 끝자락에 있는 톱니들도 양쪽을 모두 봐야하므로 가장자리에 더미 바퀴를 하나씩 추가했다.