LeetCode - High Five

문제 설명

Given a list of the scores of different students, items, where items[i] = [IDi, scorei] represents one score from a student with IDi, calculate each student's top five average.

Return the answer as an array of pairs result, where result[j] = [IDj, topFiveAveragej] represents the student with IDj and their top five average. Sort result by IDj in increasing order.

A student's top five average is calculated by taking the sum of their top five scores and dividing it by 5 using integer division.

입출력 예시

Example 1:

Input: items = [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]
Output: [[1,87],[2,88]]
Explanation:
The student with ID = 1 got scores 91, 92, 60, 65, 87, and 100. Their top five average is (100 + 92 + 91 + 87 + 65) / 5 = 87.
The student with ID = 2 got scores 93, 97, 77, 100, and 76. Their top five average is (100 + 97 + 93 + 77 + 76) / 5 = 88.6, but with integer division their average converts to 88.

Example 2:

Input: items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]
Output: [[1,100],[7,100]]

제약사항

Constraints:

1 <= items.length <= 1000
items[i].length == 2
1 <= IDi <= 1000
0 <= scorei <= 100
For each IDi, there will be at least five scores.

Solution

import java.util.HashMap;
import java.util.PriorityQueue;

/* 
최소힙을 priority queue로 구현
- 내부 자료구조는 힙(완전 이진트리)
- 시간 복잡도: O(NLogN)
*/

class Solution {
    public int[][] highFive(int[][] items) {

        int NUM_OF_SOCORE = 5;
        HashMap<Integer, PriorityQueue<Integer>> topFives = new HashMap<Integer, PriorityQueue<Integer>>();

        for (int i = 0; i < items.length; i++) {
            int id = items[i][0];
            int score = items[i][1];
            PriorityQueue<Integer> maxTopFive = topFives.get(id);

            if (maxTopFive == null) {
                maxTopFive = new PriorityQueue<Integer>();
                maxTopFive.add(score);
                topFives.put(id, maxTopFive);
            } else if (maxTopFive.size() < 5) {
                maxTopFive.add(score);
            } else {
                if (maxTopFive.peek() < score) {
                    maxTopFive.poll();
                    maxTopFive.add(score);
                }
            }

        }

        int[][] topfivesResult = topFives.entrySet().stream().map(x -> {
            int[] element = new int[2];
            element[0] = x.getKey();
            element[1] = x.getValue().stream().reduce(0, Integer::sum) / NUM_OF_SOCORE;
            return element;
        }).toArray(int[][]::new);

        return topfivesResult;
        // return null;
    }
}