귤 고르기

작성일: 2024-11-02

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/138476

접근 방식

가장 먼저 떠오른 방식은 set와 순열을 통한 방식이다.

하지만, 길이가 10만이기에 이 방식은 적합하지 않다. (너무 오래걸림)

따라서, 다른 방식을 생각해야 했다.

생각난 방식은 Hash를 이용한 방식이다.

각 숫자와 등장 횟수를 Hash로 만들고, k가 충족될 때까지 더하는 것이다. (많이 나온 숫자부터)

결과

소스 코드

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int t:tangerine){
            int cnt = map.getOrDefault(t, 0);
            map.put(t, cnt+1);
        }
        int answer = 0;
        int sum = 0;
        List<Integer> list = new ArrayList<>(map.values());
        Collections.sort(list, Collections.reverseOrder()); // 내림차순
        for(int i=0; i<list.size(); i++){
            sum+=list.get(i);
            answer++;
            if(sum>=k) break;
        }
        return answer;
    }

}

맵에 숫자 종류 별 갯수를 저장한다.

저장된 갯수만으로 리스트를 생성한 뒤, 내림차순하여 가장 많은 갯수를 가진 숫자부터 더해간다.

더했을 때, 충족해야하는 k를 넘어선다면 종료

다른 접근 방식

없음.

알게 된 점

없음.