[백준] 1021 회전하는 큐

백준 1021번 회전하는 큐

자료구조 / 덱

 

 

 

[문제]

 

 

[과정]

 

데큐가 기본 리스트보다 속도면에서 우위가 있음

리스트: O(N) 데큐: O(1)

 

※ deque 함수 정리

• q.appendleft(v) : 왼쪽에 개체v를 추가
• q.append(v) : 오른쪽에 개체v를 추가
• q.index(v) : q에서 v가 있는 인덱스 반환
• q.popleft() : 큐의 맨 왼쪽에 있는 개체를 반환 후 삭제
• q.pop() : 큐의 오른쪽에 있는 개체를 반환 후 삭제
• q.rotate(-v) : 큐를 오른쪽으로 v만큼 회전             # 숫자가 -2라면 오른쪽으로 2만큼 회전
• q.rotate(v) :  큐를 왼쪽으로 v만큼 회전
• q.reverse() : 큐 뒤집기

 

※ 핵심 풀이

찾으려는 데이터의 큐의 인덱스와 (큐의 크기 / 2)를 비교 했을 때 작거나 같으면 오른쪽으로 회전, 크다면 왼쪽으로 회전

 

 

[소스코드]

 

# 1021 회전하는 큐

from collections import deque

n,m = map(int, input().split())
data = list(map(int, input().split()))
q = deque()
for i in range(1, n+1):
    q.append(i)

ans = 0
idx = 0
while idx <m:
    if q[0] == data[idx]:
        q.popleft()
        idx += 1
    else:
        cnt = q.index(data[idx])
        if cnt <= len(q) / 2:
            q.rotate(-1)
            ans += 1
        else:
            q.rotate(1)
            ans += 1
print(ans)

 

---

 

[통과]