Daily LeetCode Challenge - 2462. Total Cost to Hire K Workers

Problem From.

https://leetcode.com/problems/total-cost-to-hire-k-workers/

오늘 문제는 costs 배열이 주어지고, 후보자의 수인 candidates 가 주어질때, k 만큼의 일꾼을 뽑아서 임금이 가장 적게 드는 경우를 구하는 문제였다.
candidates 는 costs 배열에서 앞에서 candidates 만큼, 뒤에서 candidates 만큼의 사람을 봐서 그 중의 최솟값을 반환하는데 쓰인다.

이 문제는 priority queue 두개를 사용하여 풀 수 있었는데, 먼저 왼쪽에서부터 원소를 넣는 priority queue 를 만들고, 그 다음 오른쪽에서부터 원소를 넣는 priority queue 를 하나 더 만들어서, 두 원소가 겹치지않게 넣어준다. 그 다음 두 queue 를 비교하면서 최솟값을 구하고, 서로의 queue 의 원소가 겹치지 않도록, 원소를 추가해주면 되었다.

import java.util.*

class Solution {
    fun totalCost(costs: IntArray, k: Int, candidates: Int): Long {
        
        var answer = 0L
        var left = 0
        var right = costs.lastIndex
        val leftQ = PriorityQueue<Long>()
        val rightQ = PriorityQueue<Long>()
        var n = k
        
        while(n > 0) {
            while(leftQ.size < candidates && left <= right) leftQ.add(costs[left++].toLong())
            while(rightQ.size < candidates && left <= right) rightQ.add(costs[right--].toLong())
            
            if(leftQ.peek() ?: 100001 <= rightQ.peek() ?: 100001) {
                answer += leftQ.poll()
            }else {
                answer += rightQ.poll()
            }
            n -= 1
        }
        
        return answer
        
    }
}