프로그래머스 Level2 프린터

프린터

출처: 프로그래머스

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

프로그래머스

 

문제 풀이

문제에 대해 간단히 설명드리면 

인쇄 요청을 하는 배열이 들어옵니다.

이제 인쇄 요청대로 맨 앞의 문서부터 프린터하려고 하는데 각 문서마다 고유한 우선순위가 있습니다.

맨 처음 순서에 인쇄하려는 문서를 확인해보니 이 문서보다 우선순위가 높은 문서가 목록에 있으면 

이 손에 들고있는 문서를 요청 목록 맨 뒤에 다시 넣습니다. 그리고 다시 맨 앞에서 문서 하나를 꺼내고 우선순위를 확인하고 제일 우선순위가 높은 문서이면 처리하고 아니면 다시 맨 뒤로 넣고 반복하는 겁니다.

근데 여기서 한 사람이 처음 요청 목록에 3번째에 자기 문서가 있다고 가정하고 요청 목록 3번째에 있는 자신의 문서가 언제 처리가 되는지 알고싶다는 겁니다. 

 

처음 생각한 건 

아래와 같은 코드입니다.

선행으로 아이템을 먼저 지정해두고 while 반복을 통해 ArrayDeque에서 확인하는 솔루션입니다.

count로 만약에 맨 앞의 문서보다 value 값이 큰 item이 있으면 앞에서 빼고 뒤로 넣고 item이 내가 찾는 findingitem이면 스탑하고 그때의 answer를 반환합니다.

class Solution {
    fun solution(priorities: IntArray, location: Int): Int {
        var answer = 0
        val queue = ArrayDeque<Item>()
        val findingItem = Item(value = priorities[location], location = location)
        priorities.forEachIndexed { index, i ->
            val data = Item(
                value = i,
                location = index
            )
            queue.add(data)
        }
        while(queue.isNotEmpty()) {
            val first = queue.first()
            if(queue.count { it.value > first.value } != 0 ) {
                queue.addLast(first)
                queue.removeFirst()
            } else {
                if(first == findingItem) break
                else {
                    queue.removeFirst()
                    answer++
                }
            }
        }

        return answer+1
    }
}

data class Item(
    val value: Int,
    val location: Int
)

 

효율은 아래와 같습니다.

좀 더 생각해보니 이것보다 더 빠르게 풀 수 있을 것 같다는 생각이 들었습니다.

먼저, count를 세는건 비효율적입니다.

find 함수를 통해 찾아볼까도 했지만 만약 존재하지 않는다면 그때도 결국 n을 한 번 다 돌아야하기 때문에 내키지 않았습니다.

 

곰곰히 생각해보니 여기서 PriorityQueue를 사용해서 해보자! 라는 아이디어가 떠올랐고 시도해보았습니다.

 

이게 훨씬 재밌습니다.

 

PrirorityQueue를 이용한 최대힙 과정의 풀이

 

처음에는 Document data class를 만들어서 deq이랑 priorityQ에 둘 다 넣어줬습니다.

import java.util.*

class Solution {
    fun solution(priorities: IntArray, location: Int): Int {
        var answer = 1
        val deq = ArrayDeque<Document>()
        val priorityQ = PriorityQueue<Document>(compareBy{-it.priority})
        priorities.forEachIndexed { i, p ->
            val doc = Document(i,p)
            deq.addLast(doc)
            priorityQ.add(doc)
        }
        while(deq.isNotEmpty()) {
            val currentDoc = deq.removeFirst()
            if(currentDoc.priority < priorityQ.peek().priority) {
                deq.addLast(currentDoc)
            } else {
                priorityQ.poll()
                if(currentDoc.index == location) break
                else answer++
            }
        }
        return answer
    }
}

 data class Document(
     val index : Int,
     val priority: Int
 )

 

위와 같이 풀었을때 효율성은 아래와 같습니다. 맨 처음보다는 좋아졌습니다.

 

한 번더 코드를 곰곰히 살펴보니, PriorityQueue에 굳이 Document를 넣지 않아도 되겠다 생각했습니다.

index를 사용하지 않는데 필요할까라는 생각에 코드를 수정하였습니다.

아래와 같습니다.

변경한 부분은 prirorityQ 변수 타입을 Int로 변경하고 priorities.forEach안에 -p를 넣어서 큰 수가 위로 가게 해줍니다.

그리고 밑에 while문 안에 if를 보시면 -priorityQ.peek()으로 다시 -를 사용하여 양수로 바꿔줍니다.

import java.util.*

class Solution {
    fun solution(priorities: IntArray, location: Int): Int {
        var answer = 1
        val deq = ArrayDeque<Document>()
        val priorityQ = PriorityQueue<Int>()
        priorities.forEachIndexed { i, p ->
            val doc = Document(i,p)
            deq.addLast(doc)
            priorityQ.add(-p)
        }
        while(deq.isNotEmpty()) {
            val currentDoc = deq.removeFirst()
            if(currentDoc.priority < -priorityQ.peek()) {
                deq.addLast(currentDoc)
            } else {
                priorityQ.poll()
                if(currentDoc.index == location) break
                else answer++
            }
        }
        return answer
    }
}

 data class Document(
     val index : Int,
     val priority: Int
 )

 

효율을 보시면 조금이지만 확실히 줄어든게 보입니다. 

PrirorityQ에서 Document 객체를 사용하지 않으므로 시간이 줄어들었습니다.

 

하나 더 추가로 해본건 Pair를 쓰면 어떨까 였는데

 

큰 차이가 없습니다. 

Pair도 data class여서 크게 다르지 않아 그런것 같습니다.

의미있는 변경은 아니었다!

1번에서의 결론은! 우선순위 큐를 이용해 현재 순위가 낮으면 뒤에 넣고 확인하는게 더 빠르다!

 

문제를 풀면서 여러가지 궁금한 것들이 있는데 그 중 하나 블로그 링크를 남깁니다.

정렬 방식은 어떨까 하고 시도해봤는데 갑자기 kotlin에서의 정렬방식이 궁금해 샛길로 빠져서 찾아보다가 재밌는 블로그가 있어서 한 번 읽어보시라고 남기고 갑니다.

정말 가도가도 끝이 없습니다. Prirority Queue도 더 파봐야겠습니다. 재밌네요.

https://ongveloper.tistory.com/385

[Kotlin/Java] Kotlin/java의 sort 동작 방식 (2022.10.18 수정)

 

아무튼 이렇게 문제를 풀어봤습니다. 읽어주셔서 감사합니다!~ 안녕~~~~