[Algorithm] BOJ 1021 회전하는 큐

틀린 부분 또는 더 효율적인 접근법에 대해 피드백 주시면 감사하겠습니다!

---

BOJ 1021 회전하는 큐

---

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

입출력 및 예제

---

풀이

---

처음 직감

• deque로 풀면 되겠다고 생각했다.
  • 문제에서 0번째 인덱스에서 pop을 하고 있다. 일반 python list에서 0번째 인덱스를 pop한 경우, O(n)의 시간복잡도가 걸린다(참조). 고로, deque.popleft()를 쓰면 될 것이라 생각했다.

    The list.pop(0) operation is almost 1000 times slower than deque.popleft. Consequently, the whole program finishes with twice the time. This is the difference between O(1) time complexity function v.s. O(n) one.

• 또한, 회전의 경우 deque.rotate(n)를 활용하면 가볍게 풀 수 있을 것이라 생각했다.
• 하지만 rotate로 n만큼 이동하는 시간보다 그냥 한번에 slicing하는 방법으로 더 빠르게 수행할 수 있지 않을까 생각했다.
  • list indexing을 생각해서 queue[target:] + queue[:target]식으로 queue를 한번에 target 인덱스가 바로 앞으로 오게 만드려는 생각이었으나....
  • deque에서는 list indexing이 안된다는 것을 이제 알았다.....
  • 결국, rotate를 사용해 수행하기로 결정

방법

• 먼저, n만큼의 queue를 만들어놓는다. (deque 사용)
• input으로 받은 target index를 다 사용할 때까지 반복
  • 현재 순번의 target 값을 뽑아, queue에서 찾는다.
  • 0번째 포인터에서 queue에서 target값이 있는 곳까지 왼쪽이 더 적게 이동하는지, 오른쪽이 더 적게 이동하는지 계산한다.
  • 그만큼 이동(deque.rotate사용)하고 count 해준다.
  • queue에서 target 값 제거한다.
• count 출력

유의

• deque 활용법만 안다면 매우 쉬운 문제였다.
• rotate(n)
  • n이 음수면, 왼쪽으로 이동
  • n이 양수면, 오른쪽으로 이동

---

코드

---

from collections import deque

n, m = map(int, input().split())
target = deque(map(int, input().split()))
q = deque([x for x in range(1, n+1)])
cnt = 0
while len(target):
    t = target.popleft()
    t_point = q.index(t)
    if t_point != 0:
        if len(q)-t_point > t_point:
            q.rotate(-t_point)
            cnt += t_point
        else:
            q.rotate(len(q)-t_point)
            cnt += len(q)-t_point
    q.popleft()
print(cnt)

---

느낀점

알고리즘을 다시 시작했다.
오랜만에 푸니 쉬운문제부터 쉽지 않네.
못 풀수도 있지 뭐. 처음부터 다시 시작하는 마음으로.

참조

• https://www.acmicpc.net/problem/1021