leetcode link

Description

You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the ith worker.

You are also given two integers k and candidates. We want to hire exactly k workers according to the following rules:

• You will run k sessions and hire exactly one worker in each session.
• In each hiring session, choose the worker with the lowest cost from either the first candidates workers or the last candidates workers. Break the tie by the smallest index.
  • For example, if costs = [3,2,7,7,1,2] and candidates = 2, then in the first hiring session, we will choose the 4th worker because they have the lowest cost [3,2,7,7,1,2].
  • In the second hiring session, we will choose 1st worker because they have the same lowest cost as 4th worker but they have the smallest index [3,2,7,7,2]. Please note that the indexing may be changed in the process.
• If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index.
• A worker can only be chosen once.

Return the total cost to hire exactly k workers.

---

비용 배열 costs가 주어집니다. 이 배열은 0번부터 인덱싱되며 costs[i]는 i번째 근로자를 고용하는데 필요한 비용입니다.

또한 정수 k와 candidates가 주어집니다. 다음 규칙에 따라 정확히 k명의 근로자를 고용하고자 합니다:

• k 세션을 진행하며 각 세션에서 정확히 한 명의 근로자를 고용합니다.
• 각 고용 세션에서는 처음 candidates명의 근로자들 또는 마지막 candidates명의 근로자들 중에서 가장 비용이 낮은 근로자를 선택합니다. 비용이 같을 경우 인덱스가 가장 작은 근로자를 선택합니다.
  • 예를 들어, costs = [3,2,7,7,1,2]이고 candidates = 2라면 첫 번째 고용 세션에서는 4번째 근로자를 선택하게 됩니다. 그들은 가장 낮은 비용 [3,2,7,7,1,2]을 가지고 있습니다.
  • 두 번째 고용 세션에서는 1번째 근로자를 선택하게 됩니다. 그들은 4번째 근로자와 같은 최저 비용을 가지지만 인덱스가 더 작습니다. 인덱싱이 과정에서 변경될 수 있습니다.
• 남아 있는 근로자가 candidates보다 적을 경우, 그 중에서 가장 낮은 비용을 가진 근로자를 선택합니다. 비용이 같을 경우 가장 작은 인덱스를 가진 근로자를 선택합니다.
• 한 근로자는 한 번만 선택될 수 있습니다.

정확히 k명의 근로자를 고용하기 위한 총 비용을 반환하세요.

예제 1:

입력: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
출력: 11
설명: 총 3명의 근로자를 고용합니다. 초기 총 비용은 0입니다.

• 첫 번째 고용 라운드에서 [17,12,10,2,7,2,11,20,8]에서 근로자를 선택합니다. 가장 낮은 비용은 2이며, 가장 작은 인덱스인 3을 통해 비용을 결정합니다. 총 비용 = 0 + 2 = 2.
• 두 번째 고용 라운드에서 [17,12,10,7,2,11,20,8]에서 근로자를 선택합니다. 가장 낮은 비용은 2 (인덱스 4). 총 비용 = 2 + 2 = 4.
• 세 번째 고용 라운드에서 [17,12,10,7,11,20,8]에서 근로자를 선택합니다. 가장 낮은 비용은 7 (인덱스 3). 총 비용 = 4 + 7 = 11. 첫 번째와 마지막 네 명의 근로자에서 인덱스 3 근로자가 공통적으로 나타났습니다.
  총 고용 비용은 11입니다.

예제 2:

입력: costs = [1,2,4,1], k = 3, candidates = 3
출력: 4
설명: 총 3명의 근로자를 고용합니다. 초기 총 비용은 0입니다.

• 첫 번째 고용 라운드에서 [1,2,4,1]에서 근로자를 선택합니다. 가장 낮은 비용은 1이며, 가장 작은 인덱스인 0을 통해 비용을 결정합니다. 총 비용 = 0 + 1 = 1. 1번과 2번 인덱스의 근로자가 처음과 마지막 3명의 근로자에서 공통적으로 나타났습니다.
• 두 번째 고용 라운드에서 [2,4,1]에서 근로자를 선택합니다. 가장 낮은 비용은 1 (인덱스 2). 총 비용 = 1 + 1 = 2.
• 세 번째 고용 라운드에서는 candidates가 세 명보다 적습니다. 남아 있는 근로자 [2,4]에서 근로자를 선택합니다. 가장 낮은 비용은 2 (인덱스 0). 총 비용 = 2 + 2 = 4.
  총 고용 비용은 4입니다.

제약 조건:

• 1 <= costs.length <= 105
• 1 <= costs[i] <= 105
• 1 <= k, candidates <= costs.length

Solution

class Solution {
    public long totalCost(int[] costs, int k, int candidates) {
        // 두 큐를 초기화합니다. 각 큐는 배열의 양 끝에서 시작하여 비용을 관리합니다.
        PriorityQueue<Integer> leftQueue = new PriorityQueue<>();
        PriorityQueue<Integer> rightQueue = new PriorityQueue<>();

        // 양쪽 끝에서 시작하는 포인터입니다.
        int leftIndex = 0;
        int rightIndex = costs.length - 1;

        // 최종 비용을 저장할 변수입니다.
        long totalCost = 0;

        // k명의 근로자를 선택합니다.
        while (k-- > 0) {
            // leftQueue에 candidates 수만큼 원소를 추가합니다.
            while (leftQueue.size() < candidates && leftIndex <= rightIndex) {
                leftQueue.offer(costs[leftIndex++]);
            }
            // rightQueue에 candidates 수만큼 원소를 추가합니다.
            while (rightQueue.size() < candidates && leftIndex <= rightIndex) {
                rightQueue.offer(costs[rightIndex--]);
            }

            // 각 큐에서 최소값을 비교합니다.
            int minLeft = leftQueue.isEmpty() ? Integer.MAX_VALUE : leftQueue.peek();
            int minRight = rightQueue.isEmpty() ? Integer.MAX_VALUE : rightQueue.peek();

            // 더 작은 비용의 근로자를 선택하고 해당 큐에서 제거합니다.
            if (minLeft <= minRight) {
                totalCost += minLeft;
                leftQueue.poll();
            } else {
                totalCost += minRight;
                rightQueue.poll();
            }
        }

        return totalCost;
    }
}