[백준] 1021번 회전하는 큐

사용 언어 - Python3

10866번: 덱 (실버4, 큐)

문제 ★큐 문제★

1021번: 회전하는 큐

 

 

정답

deque([]) 사용하기

(코드 풀이)

<1번 연산>

위치값이 큐의 첫번째 원소와 같으면 큐 앞에 있는 원소를 pop한다.

<2번 연산>

q의 i번째 위치값 < q 길이의 절반 인 경우,

맨 왼쪽의 원소를 q의 맨 뒤로 append한다. q의 첫번째 원소가 i가 될때까지 반복한다.

<3번 연산>

q의 i번째 위치값 > q 길이의 절반 인 경우,

맨 오른쪽의 원소를 q의 맨 앞으로 appendleft 한다. q의 첫번째 원소가 i가 될때까지 반복한다.

 

2,3번 연산을 할 때만 count += 1로 count값을 센다.

 

# 정답

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int,input().split()) #큐의 크기 n , 뽑아내려는 개수 m
loc = list(map(int,input().split())) #뽑으려는 위치값
q = deque([ _ for _ in range(1,n+1)]) #1~n 큐

count = 0
for i in loc:
    while True:
        if q[0] == i: #가장 최소위치가 가장 앞이라면 앞에 있는 원소 다 삭제
            q.popleft()
            break
        else:
            if q.index(i) < len(q)/2: #q의 i번째 위치 < q 길이의 절반
                while q[0] != i: #q의 첫번째 원소가 i가 될때까지 반복
                    q.append(q.popleft()) # 맨왼쪽 원소를 맨 뒤로 보내기
                    count += 1
            else:
                while q[0] != i :
                    q.appendleft(q.pop()) # 맨오른쪽 원소를 맨 앞으로 보내기
                    count += 1
print(count)

 

---

레퍼런스

• 정답 참고

[Algorithm] 백준 1021번 회전하는 큐(파이썬)

• 깃허브 정답

GitHub - yyeongeun/codingtest: 코딩테스트 공부