[파이썬] 프로그래머스 - 프린터

---

📌  Deque

A Double-ended Queue

 

Double-ended는 양 끝에 elements를 추가/삭제를 지원한다는 의미 한다.

Deque 주요 함수

• append() : deque의 right end에 요소 추가
• appendleft() :  deque의 lef end에 요소 추가
• pop() : deque의 right end의 요소 삭제
• popleft() : deque의 left end의 요소 삭제

 

 

뒤에서 추가/삭제는 덱과 리스트는 속도 차이가 없지만, 첫 번째 원소를 추가 삭제한다면 극명한 속도 차이가 발생한다.

 

첫번째 원소를 삭제하면 그림처럼 삭제 후 모든 원소를 앞으로 이동시키기 때문에 시간 복잡도가 O(n)이기 때문이다.

 

 

 

 

📌  풀이

핵심은 어떻게 location을 내가 인쇄를 요청한 원소에 맞춰 변경해 주느냐 이다.

나는 우선 deque의 가장 왼쪽에 있는 원소와 deque 중 가장 큰 원소를 비교하여 가장 왼쪽에 있는 원소가 가장 큰 원소냐 아니냐에 따라 분리해주었다.

 

만약 가장 큰 원소가 아니면서 location이 0이라면 맨 뒤로 보내주면서 location을 가장 뒷 index 즉 len(deq) - 1로 바꿔준다.

0이 아니라면 한 칸씩 앞으로 오게 될 것이므로 location을 location -= 1을 통해 조정해준다.

 

만약 deque의 가장 왼쪽에 있는 원소가 deque 중 중요도가 가장 큰 원소라면 그 원소의 location이 0인지 확인해준다. (같은 중요도의 원소가 여러 개 일 수 있으므로) 그 뒤 location이 0이 아니라면 해당 원소는 pop 시켜주고 location을 1 줄여주면서 순위가 밀려났으므로 temp를 1 늘려준다.

 

만약 location이 0이라면 해당 원소가 deque 중 중요도가 가장 큰 원소이면서 내가 인쇄를 요청한 원소가 되므로 temp 값을 리턴해주어 답을 도출한다.

 

코드

from collections import deque

def solution(priorities, location):
    deq = deque(priorities)
    temp = 1
    while True:
        if deq[0] < max(deq):
            if location != 0:
                location -= 1
                deq.append(deq.popleft())
            else:
                location += len(deq) - 1
                deq.append(deq.popleft())
        elif deq[0] == max(deq):
            if 0 != location:
                location -= 1
                temp += 1
                deq.popleft()
            else:
                return temp