[kotlin] 프로그래머스 - 명예의 전당(1) / PriorityQueue

문제 설명

"명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 시청자들의 문자 투표수로 가수에게 점수를 부여합니다. 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념합니다. 즉 프로그램 시작 이후 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 됩니다. k일 다음부터는 출연 가수의 점수가 기존의 명예의 전당 목록의 k번째 순위의 가수 점수보다 더 높으면, 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다.

이 프로그램에서는 매일 "명예의 전당"의 최하위 점수를 발표합니다. 예를 들어, k = 3이고, 7일 동안 진행된 가수의 점수가 [10, 100, 20, 150, 1, 100, 200]이라면, 명예의 전당에서 발표된 점수는 아래의 그림과 같이 [10, 10, 10, 20, 20, 100, 100]입니다.

명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 매일 발표된 명예의 전당의 최하위 점수를 return하는 solution 함수를 완성해주세요.

 

 

입출력 예

k	score	result
3	[10, 100, 20, 150, 1, 100, 200]	[10, 10, 10, 20, 20, 100, 100]
4	[0, 300, 40, 300, 20, 70, 150, 50, 500, 1000]	[0, 0, 0, 0, 20, 40, 70, 70, 150, 300]

 

---

접근 방법1

내 생각이 얼마나 단순했냐면

1. score랑 result랑 size도 같고 score 요소가 사용되네ㅋ? > map 사용

2. score 배열 잘라서 그 중 3번째로 작은 거 반환하면 되겟네? > slice, sort 사용

3. 매번 sort하는 거 시간 오래 걸릴텐데... > 근데 다른 아이디어도 없고... 함수를 단일 표현으로 끝낼 수 있는데... 단일 표현 함수 짧아서 멋진데...

라는 생각으로 아래 코드가 탄생함...ㅋ

 

답은 맞지만 당연하게도 시간이 너무 오래 걸림...ㅋ

class Solution {
    fun solution(k: Int, score: IntArray): IntArray = score.mapIndexed{ i, s ->
            if(i+1 < k) score.slice(0..i).sorted()[0]
            else score.slice(0..i).sortedDescending()[k-1]
        }.toIntArray()
}

 

 

접근 방법2

다른 사람 풀이를 보니까 PriorityQueue를 사용해서 문제를 해결하는 게 가장 효율적으로 보였음

시간 복잡도로만 봐도 나는... n인데 우선순위 큐 사용하면 logn임

시간도 적게 걸리고, 나의 경우 sort를 사용했는데 우선순위 큐를 사용하면 자동 정렬이 된다는 점에서 멋진 아이디어라고 생각했다...

 

1. score 배열 순서대로 한 요소씩 접근

2. k 이전 요소까지는 모두 순위에 오르니까 PriorityQueue에 저장

2-1. PriorityQueue는 자동으로 오름차순으로 정렬해주니까 peek를 했을 때 가장 작은 값을 얻을 수 있음

3. k 이후 요소부터는 peek 값보다 큰 요소만 PriorityQueue에 저장

4. 작은 값은 삭제

import java.util.*

class Solution {
    fun solution(k: Int, score: IntArray): IntArray {
        val pq = PriorityQueue<Int>()
        val answer = mutableListOf<Int>()
        
        score.forEach {
            if(pq.size < k) {
                pq.offer(it)
            } else {
                if(pq.peek() < it) {
                    pq.poll()
                    pq.add(it)
                }
            }
            answer.add(pq.peek())
        }
        
        return answer.toIntArray()
    }
}

---

PriorityQueue(우선순위 큐)

이진 트리 형태로 값을 오름차순 또는 내림차순으로 정렬할 수 있는 큐이다.

// 오름차순
val pq = PriorityQueue<Int>()
// 내림차순
val pq = PriorityQueue<Int>(Collections.reverseOrder())

• 확인: 트리의 top값을 읽음(최소값 또는 최대값을 알아낼 수 있음)
  • element(): E
  • peek(): E?
  • element는 큐 비어있으면 NoSuchElementException 오류가 남. peek의 경우 null 반환. peek 쓰는 게 더 나음요
•  삽입
  • add(element: E): Boolean
  • offer(element: E): Boolean
  • 둘 다 삽입, 삽입 후 성공하면 true 반환이지만
  • add는 삽입 시 여유 공간 없으면 IllegalStateException 오류가 남. offer는 걍 false 반환하기 때문에 offer 사용이 더 좋을 듯
• 삭제
  • remove(): E
  • poll(): E?
  • remove는 큐 비어있으면NoSuchElementException 오류가 나지만 poll은 null 반환함. poll이 더 낫겟죠.