항해99 알고리즘 마라톤 30번 문제 [백준 1021번]

 

1021번: 회전하는 큐

핵심요소

1. 큐를 어떻게 회전시킬 수 있을까?
2. 큐를 언제 좌,우로 회전시켜야 할까?

문제풀이

큐를 좌측으로 회전시킬 때는 List에서 첫 번째 인자를 뺀 후 뒤에 삽입하고,

큐를 우측으로 회전시킬 때는 List에서 마지막 인자를 뺀 후 맨 앞에 삽입하면 된다.

이러한 형태로 큐 회전 함수를 구현해보았다.

 

 

그러면 큐를 언제 회전시켜야 할까?

 

큐의 이동 거리

 

큐를 회전시킬 때 가운데를 기준으로 왼쪽으로 가까울수록 좌측회전이 이동 경로가 짧고

가운데를 기준으로 오른쪽으로 갈수록 우측회전이 이동 경로가 짧다.

즉, 큐에서 찾고자 하는 값이 가운데를 기준으로 우측에 있으면 우회전, 좌측에 있으면 좌회전을 하도록 구현해야 한다.

 

 

해당하는 값에 도달하였을 때

입력받은 데이터가 포함된 List와 설정한 Queue의 List 첫 번째 인자를 pop(0)으로 추출하도록 구현한다.

 

 

 

 

그런데 뭔가 더 개선할 수 있는 부분이 있는 것 같다.

pop(0)의 경우 시간복잡도가 O(n)으로 비효율적이고,

left_queue(), right_queue() 함수를 구현하지 않고 라이브러리만으로도 사용할 수 있을 것 같다.

 

파이썬 라이브러리 증에서 collections.deque에서는 이러한 것들이 이미 구현되어 있다.

deque.popleft()로 좌측에 해당하는 인자를 O(1)의 시간복잡도로 꺼내올 수 있으며,

deque.rotate() 함수로 해당하는 deque를 좌측 또는 우측으로 회전할 수 있다.

 

그러면 해당하는 부분을 수정해보도록 하자

 

성공적으로 작성이 완료되었다.