2462. Total Cost to Hire K Workers

문제

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

풀이

class Solution {
    public long totalCost(int[] costs, int k, int candidates) {
        PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> {
            if(costs[a] == costs[b]) {
                return a - b;
            }
            return costs[a] - costs[b];
        });

        int left = 0;
        int right = costs.length - 1;
        long answer = 0;

        for(int i = 0; i < candidates; i++) {
            heap.add(left++);
        }

        if(left <= right) {
        for(int i = 0; i < candidates && left <= right; i++) {
            heap.add(right--);
            }
        }

        for(int i = 0; i < k; i++) {
            int index = heap.poll();
            answer += costs[index];
            if(left <= right) {
                if(index < left) {
                    heap.add(left++);
                } else {
                    heap.add(right--);
                }
            }
        }

        return answer;
        
    }
}

• left만큼 heap에 넣어주고, 만약 left만큼 넣어줬어도 right 부분이 남아있다면 그 부분만큼 다시 heap에 넣어줌
• poll했을 때, left <= right, 즉 더 넣어줄 요소가 존재한다면 넣어주기
  • 이 때, index < left면 왼쪽 candidate에서 빠진것이므로 left에서 넣어주면 됨