[LeetCode-자바] N_2462 Total Cost to Hire K Wokers

0woy·2024년 5월 18일

Java PriorityQueue leetcode

코딩테스트

목록 보기

18/42

📜 문제

해독부터 어려운 문제다..

costs 배열에 고용 비용이 주어진다.
한 번에 1명씩 K명을 고용한다.
앞에서 candidate, 뒤에서 candidate 만큼의 비용을 비교해 가장 적은 비용을 저장한다.
남은 고용 해야하는 사람 수 < candidate인 경우 전체 배열에서 가장 적은 비용을취한다.

candidate의 용도를 이해하는 게 어려웠다. ㅠ
candidate가 3인경우 앞에서 3명, 뒤에서 3명 중 가장 적은 비용을 취하면 된다.

두 개의 우선순위 큐를 이용하여 문제를 풀어나간다.

❓ 우선순위 큐

우선순위 큐는 삽입 순서에 상관 없이 deque 될 때 우선순위에 맞게 나간다.
우선순위는 프로그래머가 결정할 수 있지만, 이 문제에서는 우선순위를 변경하지 않아도 된다.

그 이유는, 그림의 natural ordering을 살펴보면,
우선순위가 Collection.sort로 자동 정렬되어 deque할 때 작은 순서대로 빠져나간다.

문제에서 각 candidate 중 적은 비용을 취하므로 우선순위를 따로 조작하지 않아도된다.

✍ 부분 코드 설명

변수 선언

   public long totalCost(int[] costs, int k, int candidates) {
         PriorityQueue<Integer> pq1 = new PriorityQueue<>();
        PriorityQueue<Integer> pq2 = new PriorityQueue<>();
        int front =0;
        int end =costs.length-1;
        long sum =0;
       ...

- p1: 앞에서부터 candidate 만큼을 저장하는 우선순위 큐
- p2: 뒤에서부터 candidate 만큼을 저장하는 우선순위 큐
- front: p1에 사용할 인덱스
- end: p2에 사용할 인덱스
- sum: k명의 고용 비용을 저장하는 변수

우선순위 큐 저장 & 적은 비용 찾기

		...
        
	 while(k-- >0){
            while(pq1.size()<candidates && front<=end){
                pq1.offer(costs[front++]);
            }
            while (pq2.size()<candidates&&front<=end){
                pq2.offer(costs[end--]);
            }
            int v1 = pq1.size()>0?pq1.peek():Integer.MAX_VALUE;
            int v2 = pq2.size()>0?pq2.peek():Integer.MAX_VALUE;
            if(v1<=v2){
                sum+=v1;
                pq1.poll();
            }
            else{
                sum+=v2;
                pq2.poll();
            }
        }
        return sum;

k명을 고용할 때까지 반복
candidate 수만큼 pq1, pq2에 원소 삽입
v1, v2 변수에 각각 pq1, pq2의 가장 적은 원소 저장
- 큐가 비어 있는 경우, Integer.MAX_VALUE 저장
v1, v2 비교 후, 더 적은 수 sum에 저장

while 문 내의 front<=end 조건이 중요하다고 생각한다.
front>end인 경우, 이미 q2에 저장된 원소를 q1에 삽입하거나 그 반대의 경우가 이루어질 수 있기 때문에 유효한 답을 낼 수 없다.

그림으로 알아보자!

k=2일 때, q2의 2가 선택되고, k=1로 넘어간다.
이때, q2가 추가되지 않는데, front <= end의 조건을 충족하지 못했기 때문이다.

🍳 전체 소스 코드

class Solution {
    public long totalCost(int[] costs, int k, int candidates) {
         PriorityQueue<Integer> pq1 = new PriorityQueue<>();
        PriorityQueue<Integer> pq2 = new PriorityQueue<>();
        int front =0;
        int end =costs.length-1;
        long sum =0;
        while(k-- >0){
            while(pq1.size()<candidates && front<=end){
                pq1.offer(costs[front++]);
            }
            while (pq2.size()<candidates&&front<=end){
                pq2.offer(costs[end--]);
            }
            int v1 = pq1.size()>0?pq1.peek():Integer.MAX_VALUE;
            int v2 = pq2.size()>0?pq2.peek():Integer.MAX_VALUE;
            if(v1<=v2){
                sum+=v1;
                pq1.poll();
            }
            else{
                sum+=v2;
                pq2.poll();
            }
        }
        return sum;
    }
}