[python]1966_프린터 큐

1 걸린 시간 : 45m

2 사용한 자료구조 및 개념 : deque

---

💡 문제풀이 아이디어 및 어려웠던 점

---

💫 아이디어

    1️⃣ enumerate와deque를 사용하여 기존 순서와 값을 가진 튜플 리스트를 만든다

    2️⃣ 최댓값과 현재 프린트될 순서의 값을 popleft()하여 비교

    3️⃣ 같으면 출력 횟수 +1을 해주고 출력 후 break

    4️⃣ 다르다면 append하여 리스트의 끝으로 낸다

---

👻 어려웠던 점

 

🚨 최적화된 방법인가?

중요도가 높은 문서를 찾기 위해 매번 max로 전체 리스트를 스캔하는것이 비효율적이라고 생각되어 다른 방법을 찾아보았다.
⇒ heapq 모듈을 사용하여 우선 순위 큐 구현! (아래에 또 구현코드 있음)

 

Solution Code & 주석

import sys
from collections import deque

tc = int(sys.stdin.readline())

for _ in range(tc):
    n, m = map(int, sys.stdin.readline().split())
    documents = deque(enumerate(list(map(int, sys.stdin.readline().split()))))
    cnt = 0
    while documents:
        best = max(priority for idx, priority in documents)
        now_idx, now_document = documents.popleft()
        if best == now_document:
            cnt += 1
            if now_idx == m:
                print(cnt)
                break
        else:
            documents.append((now_idx, now_document))

---

보다 최적화한 코드

import sys
from collections import deque
import heapq

tc = int(sys.stdin.readline())

for _ in range(tc):
    n, m = map(int, sys.stdin.readline().split())
    documents = deque(enumerate(map(int, sys.stdin.readline().split())))
    priority_queue = []
    for now_idx, now_document in documents:
        heapq.heappush(priority_queue, -priority)
    cnt = 0
    while documents:
        now_idx, now_document = documents.popleft()
        if priority == -priority_queue[0]:
            heapq.heappop(priority_queue)
            cnt += 1
            if now_idx == m:
                print(cnt)
                break
        else:
            documents.append((now_idx, now_document))

✔️ heapq 모듈은 최소 힙만을 지원하기 때문에 중요도가 높은 문서를 먼저 반환할려면 중요도를 음수 로 해야함!

---

메모리와 시간이 훨씬 적게 걸린 코드_백준 참고

import sys

tc = int(sys.stdin.readline())

for _ in range(tc):
    n, m = map(int, sys.stdin.readline().split())
    documents = list(map(int, sys.stdin.readline().split()))
    que = list(enumerate(documents))
    documents.sort(reverse=True)
    cnt = 0
    for now in documents:
        while que[0][1] != now:
            tmp = que.pop(0)
            que.append(tmp)
        cnt += 1
        if que.pop(0)[0] == m:
            break
    print(cnt)

• 기존 인덱스 값과 중요도 값을 가진 튜플 리스트를 하나 더 만든다
• 문서 리스트는 내림차순으로 정렬한다
• 정렬된 문서 리스트에서 최댓값을 하나씩 가져와 튜플 리스트와 비교한다
• 보다 메모리와 시간이 적게 걸린 이유
  • deque나 heapq를 사용하지 않고, 중요도가 높은 문서를 찾기 위한 과정이 sort 한 번으로 끝냈기 때문이라고 생각한다!