[Java | Algorithm] 프로그래머스 Lv2 - 귤 고르기

출처 - https://school.programmers.co.kr/learn/courses/30/lessons/138476

프로그래머스

1) 문제 설명

 

2) 접근 방식

HashMap 활용을 활용하여 귤의 크기가 많을수록 해당 크기를 우선적으로 선택하여 k를 빠르게 감소시키고
높은 빈도수부터 선택하면 귤 종류를 최소화할 수 있게 풀려고 했습니다.

3) 풀이

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        
        HashMap<Integer, Integer> map = new HashMap<>(); 
        
        for(int i : tangerine){
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        
        List<Integer> list = new ArrayList<>(map.keySet());
        
        list.sort((o1, o2) -> map.get(o2) - map.get(o1));
        
        for(int i : list){
            k -= map.get(i);
            answer ++;
            
            if(k <= 0) break;
        }
        
        return answer;
    }
}

 

1. 귤 크기별로 빈도수 저장

• HashMap<Integer, Integer>을 사용하여 귤의 크기와 해당 크기의 개수를 저장합니다.
• 키는 귤의 크기, 값은 해당 크기의 빈도수입니다.
• ex) 귤 크기 배열이 [1, 3, 2, 5, 4, 5, 2, 3]일 경우, 생성된 맵은 {1=1, 3=2, 2=2, 5=2, 4=1}가 됩니다.

getOrDefault는 Java의 Map 인터페이스에서 제공하는 메서드입니다.
주어진 키에 대해 값을 조회하거나, 키가 없을 경우 기본값을 반환하는 기능을 합니다.

 

동작 방식

1. 지정된 키(key)가 맵에 존재하면 해당 키의 값을 반환합니다.
2. 지정된 키가 맵에 존재하지 않으면 기본값(defaultValue)을 반환합니다.

2. 빈도수를 기준으로 내림차순 정렬

• 맵의 키들을 리스트로 변환한 후, 각 키에 해당하는 빈도수를 기준으로 내림차순 정렬합니다.
• ex) 위 맵의 경우, 내림차순 정렬된 리스트는 [3, 2, 5, 1, 4]가 됩니다.

 

3.최소한의 귤 종류로 k개 선택

• 정렬된 리스트를 순회하며 높은 빈도수부터 k에서 빼줍니다.
• 귤 종류를 하나 추가할 때마다 answer를 증가시킵니다.
• k가 0 이하가 되는 순간 반복을 종료하고 answer를 반환합니다.

정리

HashMap에 대해서 공부했던 적이 있어서 쉽게 풀 수 있었습니다.

자료 구조 공부의 중요성!!