[TIL 2024. 03. 13] 큐/우선순위큐 : 프린터 큐

오늘 한 일

• 오늘의 코드카타 7문제
• 오후 알고리즘 세션: bfs (queue활용)
• 알고리즘 문제 복습: 1로 만들기(while문 ver.(->시초)/dp ver.)
• TIL 작성

 

큐/우선순위큐

1. 큐(queue)

• 자료구조 중 stack이 LIFO이었다면, 큐는 stack과는 반대로 FIFO(First In First Out, 선입선출)의 자료구조이다
• 한쪽으로 들어가면, 다른 한쪽으로 빠지는 구조이므로 연산도 이에 맞춰서 사용해야 한다
• => (append, popleft)가 함께 쓰이고, (appendleft, pop)이 함께 쓰인다 (cf. 디폴트는 오른쪽임)
• from collections import deque (필수)
• deque(데크, ): 양쪽 모두에서 in,out이 가능한 자료구조
• => deque를 사용하면 queue는 물론 stack도 만들 수 있다

 

2. 우선순위큐(priority queue) 

• 우선순위큐는 우선순위가 가장 높은 자료를 가장 먼저 꺼내는 자료구조이다. 즉, 먼저 들어간 순서대로 꺼내지는 큐와 구분된다
• 이진트리인 '힙(heap)'을 통해서 구현된다 (cf. 파이썬의 디폴트는 최소힙)
• import heapq (필수)
• 주로 쓰이는 연산은 heapify(리스트를 힙으로 바꾸는 연산), heappush, heappop

 

프린터 큐(BOJ)

문제를 읽어 보고 들어야 하는 생각은..

• 중요도와 입력시의 index를 담아둘 변수를 만들어야겠다 (문제에서 최종적으로 출력하라고 하는게 특정 index의 문서가 몇 번째로 프린트 되는지?) => val, idx를 튜플이나 리스트 등으로 묶어서 관리해야 편하겠다
• 최소힙 등의 우선순위 있는 자료를 먼저 꺼내는게 아니라, popleft되면서 하나씩 빠져야 하는 것이므로 큐를 쓰면 되겠다 => val, idx를 담을 변수를 queue로 하면 되겠다.. popleft해서 쓰게.
• 반복의 횟수를 확정할 수 없으므로 while문을 쓰고, 그 조건은 queue의 요소가 있는 한. 즉, queue가 True인 경우로 하면 되겠다
• => (참고: if나 while문 등에서 빈 [], {}, queue 등의 bool값은 모두 False(=0)임) 

수정 전 (오류 난 모습): 테스트 케이스2의 queue값이  pop되지 않고 테스트 케이스3의 시작부터 입력되어 있음

 

---

오류 수정: 덱 생성과 cnt 초기화의 위치 수정

 

#입력예제 1
3		#테스트 케이스가 아래의 3개다
1 0		#테스트 케이스1
5
4 2		#테스트 케이스2
1 2 3 4
6 0		#테스트 케이스3
1 1 9 1 1 1

 

이외에도 오류가 발생했던 부분이 여러군데 있었음..

1. max와 key=lambda의 사용법 & 인덱스로 접근(튜플 전체를 val과 비교할 수는 없음)
2. cnt로 0이 아닌 1로 초기화
3. (덱 생성과 cnt 초기화의 위치)