반응형
백준 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)
[통과]
반응형
'코딩테스트 문제풀이 > beakjoon' 카테고리의 다른 글
[백준] 2910 빈도 정렬 (0) | 2022.08.18 |
---|---|
[백준] 5430 AC (0) | 2022.08.12 |
[백준] 10866 덱 (0) | 2022.08.12 |
[백준] 14503 로봇 청소기 (0) | 2022.08.12 |
[백준] 13335 트럭 (0) | 2022.08.12 |
댓글