프로그래머스: 프린터 (Kotlin)

https://programmers.co.kr/learn/courses/30/lessons/42587

코딩테스트 연습 - 프린터

프로세스

1. 단순 연결 리스트 사용: O(N^2)

1. 큐(연결 리스트)에서 문서를 꺼낸다. (total O(N))
2. 우선순위가 더 큰 문서가 있는지 연결 리스트의 모든 문서를 확인한다. (total O(N^2))
   1. 있다 -> 문서를 큐에 다시 넣는다.
   2. 없다 -> 문서를 출력(삭제)하고 removeCount++
3. 출력 문서 == location 문서 -> removeCount 반환

2. 우선순위 큐, 출력 확인용 배열 사용: O(NlogN)

1. 우선순위 큐(PQ)에 문서를 모두 넣는다. (total O(NlogN))
2. 큐에서 문서를 꺼낸다.
3. PQ에서 우선순위가 더 높은 문서가 있는지 확인한다. (total O(N))
   1. 우선순위 큐 제일 위에 있는 문서를 확인한다.
   2. 이미 출력한 문서라면(isPrinted 확인) PQ에서 제거하고 다시 확인한다.
   3. 더 높은 문서가 있다 -> 큐에 다시 넣는다
   4. 없다 -> 문서 출력, removeCount++, isPrinted에 체크
4. 출력한 문서 == 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
    }
}