leetcode - maximum performance of a team(java)

level - hard

[문제 내용]
각 팀원의 efficiency와 speed가 주어지면
거기서 k명씩 골라 그 k명의 (speed 총합) * min(efficiency)의 최대값 반환

[example 1]

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation: 
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.

[example 2]

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.

[example 3]

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72

[해결 방법]
요즘 뇌가 자꾸 조합알고리즘에 꽂혔는지 자꾸 그쪽으로 생각이 먼저 들어서
그렇게 풀었다가 시간초과 나서 다른 방식을 생각하느라 너무 오래 걸렸다.

efficiency의 최소값을 골라 곱해주어야 함으로
먼저 efficiency를 내림차순으로 정렬해 주고,
그 정렬된 순서로 k개씩 계산하는 방법으로 해결했다.

class Solution {
    public int maxPerformance(int n, int[] speed, final int[] efficiency, int k) {
        // efficiency 정렬하기 위해 index 정보 저장
        HashMap<Integer, Integer> indexes = new HashMap<>();
        for(int i=0; i<n; i++) {
            indexes.put(i, efficiency[i]);
        }

        // efficiency 내림차순으로 정렬
        ArrayList<Integer> keySet = new ArrayList<>(indexes.keySet());
        Collections.sort(keySet, new Comparator<Integer>() {
            @Override
            public int compare(Integer integer, Integer t1) {
                return Integer.compare(efficiency[t1], efficiency[integer]);
            }
        });

        // PriorityQueue를 이용하여 speed를 오름차순으로 저장
        PriorityQueue<Integer> sp = new PriorityQueue<>();
        long sum = 0, max = 0;
        for(int key : keySet) {
            sp.add(speed[key]);
            sum += speed[key];
            // efficiency 는 이미 정렬되어 있기 때문에 다음번에 있는 efficiency가 항상 최소값이다
            long performance = sum * efficiency[key];
            if(max < performance) {
                max = performance;
            }
            if(sp.size() == k) {
                // 최대 값을 구하기위해 speed에서 가장 작은 값을 빼준다
                sum -= sp.poll();
            }
        }

        return (int)(max % 1000000007L);
    }
}