Queue, heap 연습 - 프린터(프로그래머스)

0. 문제

1. 손 계획

2. 코드

import collections
import heapq

def solution(priorities, location):
    # 타겟 location 의 문서가 몇 번만에 출력되었는지 count 해가는 변수
    answer = 0

    # 입력 순서를 지키고 있는 데큐
    q1 = collections.deque()
    # 우선순위 높은 것을 꺼내기 위한 heapq 로 사용할 리스트
    q2 = []

    # 입력된 우선순위들을 두 개의 큐에 넣어준다. 단 우선순위는 부호반전하여 넣는다. (최대힙처럼 사용하기 위해)
    for i, priority in enumerate(priorities):
        doc = (-priority, i)
        q1.append(doc)
        heapq.heappush(q2, doc)

    # 두 개의 큐에서 맨 앞에 있는 값의 우선순위를 비교하며 같을 경우, 해당 문서를 처리
    # 처리할 때마다 answer +=1 하고, 만약 처리한 문서의 인덱스가 타겟인 location 과 같다면 반복문 종료
    # 같지 않다면 다시 우선순위를 나타내는 큐는 변동이 아예 없고, 입력순서 지키는 큐에서는 꺼낸 값을 맨 뒤에 append
    while True:
        cur = q1.popleft()
        if cur[0] == q2[0][0]:
            answer += 1
            heapq.heappop(q2)
            idx = cur[1]
            if idx == location:
                break
        else:
            q1.append(cur)

    return answer

+ 이후에 any() 라는 함수를 알게 되어서, any()를 사용한 코드도 작성해보았다.

나는 일반 que와 heapq 두가지를 썼던 것에 비해 any()를 활용하면 하나의 que만 있으면 되기 때문에 공간적으로는 더 절약적인 방식일 것이다. 하지만, 매번 자기 큐에 대해서 자기보다 큰 값이 있는지 비교하는 것은 O(n)이 드는 선형탐색이 될 것 같다고 생각했다. 결과가 궁금해서 각 결과를 비교해보았다.

확실히 heapq를 사용하는 쪽이 시간적으로 더 빨랐고, 메모리 사용은 그렇게 큰 차이는 없어 보인다.

왼쪽이 heap 사용, 오른쪽이 any() 사용

any()를 사용한 코드

import collections
def solution(priorities, location):
    que = collections.deque()
    for i, priority in enumerate(priorities):
        que.append((i, priority))

    answer = 0
    while True:
        cur = que.popleft()
        if any(cur[1] < x[1] for x in que):
            que.append(cur)
        else:
            answer += 1
            if cur[0] == location:
                break

    return answer