Powerfull Integer 문제의 자바 해결 방법: 효율적인 알고리즘

문제

Problem_Link

문제해결방법

1. 모든 숫자를 hashmap에 넣으면서 카운트를 한다
2. hashmap의 카운트한 숫자를 Key대로 정렬한다. 최악의 경우, O(n log n)이 나옴
3. entrySet을 ArrayList로 하여, K이상 나온 수들중 가장 큰수를 찾는다

시간복잡도: O(n log n), 공간복잡도: O(n)

https://github.com/eunhanlee/powerfullInteger/blob/master/read%20me.md

class Solution {

    /**
     * 숫자별 등장 횟수를 저장하는 해시 맵을 만들고, 이 중에서 k번 이상 등장하는 가장 큰 수를 반환합니다.
     * 만약 k번 이상 등장하는 숫자가 여러 개인 경우, 가장 큰 수를 반환합니다.
     * 만약 k번 이상 등장하는 숫자가 하나도 없는 경우, -1을 반환합니다.
     *
     * @param n         구간의 수
     * @param interval  각 구간의 시작과 끝을 나타내는 2차원 정수 배열. interval[i] = [start, end]
     * @param k         등장 횟수가 k번 이상인 숫자를 찾기 위한 최소 등장 횟수
     * @return k번 이상 등장하는 가장 큰 수. 만약 k번 이상 등장하는 숫자가 하나도 없는 경우, -1을 반환합니다.
     */
    public static int powerfullInteger(int n, int[][] interval, int k) {
				// 숫자별 등장 횟수를 저장하는 해시 맵
        Map<Integer, Integer> map = new HashMap<>(); 
        // k번 이상 등장하는 가장 큰 수, 없으면 -1
				int maxPowerful = -1; 

        // 각 구간을 순회하며 숫자별 등장 횟수를 해시 맵에 저장
        for (int i = 0; i < n; i++) {
            for (int j = interval[i][0]; j <= interval[i][1]; j++) {
                map.put(j, map.getOrDefault(j, 0) + 1);
            }
        }
       
        // 해시 맵을 정렬
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort(Map.Entry.comparingByKey());

		//k번 이상 등장하는 가장 큰 수를 찾음
        for (Map.Entry<Integer, Integer> val : list) {
            if (val.getValue() >= k) {
                maxPowerful = val.getKey();
            }
        }

        return maxPowerful;
    }
}