https://programmers.co.kr/learn/courses/30/lessons/42587
코딩테스트 연습 - 프린터
일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린
programmers.co.kr
프로세스
1. 단순 연결 리스트 사용: O(N^2)
- 큐(연결 리스트)에서 문서를 꺼낸다. (total O(N))
- 우선순위가 더 큰 문서가 있는지 연결 리스트의 모든 문서를 확인한다. (total O(N^2))
- 있다 -> 문서를 큐에 다시 넣는다.
- 없다 -> 문서를 출력(삭제)하고 removeCount++
- 출력 문서 == location 문서 -> removeCount 반환
2. 우선순위 큐, 출력 확인용 배열 사용: O(NlogN)
- 우선순위 큐(PQ)에 문서를 모두 넣는다. (total O(NlogN))
- 큐에서 문서를 꺼낸다.
- PQ에서 우선순위가 더 높은 문서가 있는지 확인한다. (total O(N))
- 우선순위 큐 제일 위에 있는 문서를 확인한다.
- 이미 출력한 문서라면(isPrinted 확인) PQ에서 제거하고 다시 확인한다.
- 더 높은 문서가 있다 -> 큐에 다시 넣는다
- 없다 -> 문서 출력, removeCount++, isPrinted에 체크
- 출력한 문서 == location 문서 -> removeCount 반환
풀이
1. 연결 리스트 사용
가장 쉬운 방법은 큐에서 문서를 꺼낼 때마다 우선 순위가 더 높은 문서가 있는지 모두 확인하는 것이다. 끝에 어떤 문서서가 있을지 알 수 없어서 매번 연결 리스트를 끝까지 탐색(O(N))해야 하므로 총 O(N^2)이 걸린다. 하지만 문서가 최대 100개이므로 O(N^2)으로 해결할 수 있다.
2. 우선순위 큐와 출력 확인용 배열 사용
우선순위 큐와 출력 확인용 배열을 사용하면 O(nlogn)으로 좀 더 빠르게 해결할 수 있다.
O(N^2)이 걸렸던 이유는 매번 다른 문서를 전부 확인해야 했기 때문이다. 따라서 다른 문서의 우선 순위를 더 빠르게 확인할 수 있다면 시간 복잡도를 줄일 수 있다.
우선순위 큐
문서를 우선순위 큐(PQ)에 따로 넣어놓으면, PQ의 맨 위에 있는 문서를 통해 순위가 더 높은 문서가 있는지 바로 확인이 가능하다.
val doc = queue.poll()
// 우선 순위가 더 높은 문서가 있는지 확인
if (doc.priority >= pq.peek().priority) {
removeCount++
isPrinted[doc.id] = true
}하지만 문제는 문서를 출력할 때 PQ에서 해당 문서를 삭제하기가 번거롭다는 것이다. 왜냐면 맨 위에 있는 문서가 우선 순위가 같은 다른 문서일 수도 있기 때문이다. PQ에서 일일이 삭제를 할 수도 있는데, 그러면 총 O(nlogn)의 시간이 걸린다.
출력 확인 배열
좀 더 빠른 방법은 출력됐음을 확인하는 배열을 사용하는 것이다. 출력할 때 PQ에서 삭제하는 것이 아니라 배열에 체크를 하고, 다음 문서를 확인할 때 PQ의 맨 위에 있는 것이 이미 출력된 문서라면 제거하고 다음 문서를 가져온다. 이렇게 하면 PQ에서 문서를 제거하는 데 총 O(N)이 걸린다.
// 출력된 문서 제거
while (isPrinted[pq.peek().id]) {
pq.poll()
}코드 (우선순위 큐)
import java.util.*
data class Document(val id: Int, val priority: Int)
class Solution {
fun solution(priorities: IntArray, location: Int): Int {
var removeCount = 0
val queue: Queue<Document> = LinkedList()
val pq = PriorityQueue(compareByDescending<Document>{it.priority})
val documents = Array<Document>(priorities.size) { i ->
Document(i, priorities[i])
}
val isPrinted = BooleanArray(documents.size)
for (doc in documents) {
queue.add(doc)
pq.add(doc)
}
while(queue.isNotEmpty()) {
// 출력된 문서 제거
while (isPrinted[pq.peek().id]) {
pq.poll()
}
val doc = queue.poll()
// 우선 순위가 더 높은 문서가 있는지 확인
if (doc.priority >= pq.peek().priority) {
removeCount++
isPrinted[doc.id] = true // 출력 체크
if (doc.id == location) break
} else {
queue.add(doc)
}
}
return removeCount
}
}
'Problem Solving > 프로그래머스' 카테고리의 다른 글
| 프로그래머스: 메뉴 리뉴얼 (Kotlin) (0) | 2022.04.11 |
|---|---|
| 프로그래머스: 입국 심사 (Kotlin) (0) | 2022.04.04 |
| (Java) 프로그래머스 - 아이템 줍기 (0) | 2022.03.12 |
| [프로그래머스] 순위 (Kotlin) - 플로이드 와샬 사용하지 않고 풀기 (0) | 2022.02.14 |
| (Kotlin) 프로그래머스 - 표 편집 [2021 카카오 채용연계형 인턴십] (0) | 2022.01.07 |