[백준] 1021번: 회전하는 큐(Python)

문제 

 

1021번: 회전하는 큐

 

---

 

제출코드 

N, M = map(int, input().split())
P = list(map(int, input().split()))
q = [i for i in range(1, N+1)]
cnt = 0

for i in range(M):
    # 위치 0과의 거리 차이로 왼쪽으로 or 오른쪽으로 이동할 지를 결정
    if q.index(P[i]) < len(q)-q.index(P[i]):
        while True:
            if q[0] == P[i]:
                del q[0]
                break
            else:
                q.append(q[0])
                del q[0]
            cnt += 1
    else:
        while True:
            if q[0] == P[i]:
                del q[0]
                break
            else:
                q.insert(0, q[-1])
                del q[-1]
                cnt += 1
print(cnt)

리스트 q의 0번째 원소를 기준으로 뽑아내려는 원소와 비교하여 동일하다면 q[0]을 삭제하고 같지 않다면 p[0]과 같아질 때까지 반복하여 수행한다. 

 

 

처음엔 리스트만을 사용하여 문제를 풀었으나 deque(데크)를 공부하다보니 조금만 수정하면 deque로도 풀 수 있겠단 생각이 들었다. 

 

 

 

따라서 이 문제를 Deque를 사용하면 아래와 같이 풀 수 있다.

from collections import deque

N, M = map(int, input().split())
P = list(map(int, input().split()))
q = deque([i for i in range(1, N+1)])
cnt = 0

for i in range(M):
    q_index = q.index(P[i])
    if q_index < len(q)-q_index:
        while True:
            if q[0] == P[i]:
                q.popleft()
                break
            else:
                q.append(q.popleft())
            cnt += 1
    else:
        while True:
            if q[0] == P[i]:
                q.popleft()
                break
            else:
                q.appendleft(q.pop())
                cnt += 1
print(cnt)

 

파이썬은 collections모듈의 deque(Double-ended queue)을 통해 큐 자료구조를 구현할 수 있어 list의 앞과 뒤 모두에서 원소의 추가와 삭제가 일어난다면, deque 모듈을 사용하여 문제를 푸는 것이 더 좋다.