[프로그래머스] 스택/큐 : 프린터 Kotlin

문제를 읽어보면 헷갈린다.

 

검사 할때마다 맨 앞의 원소가 제일 큰지 배열을 검사하게 되면 구현은 되겠지만 효율성 측면에서 좋지 않다.

 

그래서 대기목록 큐와 중요도로 정렬한 큐를 이용한다.

 

대기목록의 큐는 중요도와 index를 Pair로 잡아서 중요도로는 정렬된 큐의 값과 같은지 비교할 때 사용하고

 

index는 내가 찾던 문서인지 비교할 때 사용하자.

 

문서의 중요도를 내림차순으로 정렬하고 중요도가 문서 큐와 같으면 인쇄하고 아니면 큐의 맨 뒤로 넣어주자.

 

정렬된 문서의 중요도 순으로 인쇄되고 대기 목록은 그대로기 때문에 중요도를 정렬해도 된다.

 

이렇게 하면 매번 비교할 때마다 배열을 탐색하지 않아도 된다.

 

import java.util.*

class Solution {
    fun solution(priorities: IntArray, location: Int): Int {
        var answer = 1

        var priorityQueue:Queue<Pair<Int,Int>> = LinkedList()
        var sortedArray:Queue<Int> = LinkedList(priorities.sortedArrayDescending().toList())

        priorities.forEachIndexed{index, i ->
            priorityQueue.offer(Pair(index,i))
        }
        
        var end = false

        while(!sortedArray.isEmpty()){
            var pivot = sortedArray.poll()

            for(i in 0..priorityQueue.size-1){

                if(priorityQueue.peek().second == pivot){ // 꺼내도 된다
                    if(priorityQueue.peek().first == location){ // 내가 찾는거다
                        end = true
                        break
                    }
                    var temp = priorityQueue.poll()
                    priorityQueue.add(temp)
                    answer++
                    break
                }
                else{
                    var p = priorityQueue.poll()
                    priorityQueue.add(p)
                }
            }

            if(end) break
        }

        return answer
    }
}