[프로그래머스] 자바(Java) - 귤 고르기

🧩 문제

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

프로그래머스

 

💡 내가 작성한 코드

import java.util.*;

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

1. 각 사이즈 별로 귤의 개수를 담는 `HashMap` 선언
   • `HashMap` 클래스는 키-값 쌍을 저장하는 자료구조
   • 귤의 크기(key)와 개수(value)를 키-값 쌍으로 저장
     • ex) `[ 1, 3, 2, 5, 4, 5, 2, 3 ]` -> `{ 1=1, 2=2, 3=2, 4=1, 5=2 }`
   • `map.getOrDefault(key, defaultValue)` 메소드 사용
     • key 와 맵핑된 value 값이 존재하면 value 값을 반환, 아니면 defaultValue 값 반환
     • `map.put(i, map.getOrDefault(i, 0) + 1);` 는 i 라는 키에 대해 현재 값이 있으면 1을 더하고, 없으면 0을 시작값으로 설정하여 귤의 개수를 세는 방식
2. HashMap에 저장한 value를 list에 담기
   • 각 크기별 귤의 개수를 비교하고 정렬하기 위해 `List list = new ArrayList(map.values());` 선언
   • `map.values()` 는 HashMap에 저장된 모든 값(value)을 반환
3. 리스트에 담긴 귤의 개수를 내림차순으로 정렬
   • 문제에서 최소한의 귤 개수로 k를 만족시켜야 하기 때문에, 가장 개수가 많은 귤부터 선택
4. 내림차순 정렬한 list를 반복문으로 순회하면서, 귤의 개수를 k에서 차감
   • 귤의 개수를 계속 빼면서 k가 0 이하가 되는 순간 필요한 귤의 수가 충족된 상태이므로, 귤을 선택할 필요가 더이상 없으므로 반복문은 break 로 종료

 

🧠 배운 점

1. HashMap 을 사용하는 방법
   • HashMap은 키-값 쌍으로 데이터를 저장하며, 키를 통해 빠르게 값을 조회할 수 있는 자료구조

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i : tangerine) {
    map.put(i, map.getOrDefault(i, 0) + 1);
}​

• 위 코드에서는 `getOrDefault` 메서드를 사용하여 키가 존재하지 않을 경우 기본값을 반환하도록 했습니다.
• 이로 인해 코드가 간결해지고, 각 요소의 빈도를 쉽게 업데이트할 수 있었습니다.

  2. 그리디 알고리즘에 대하여

• 매 선택에서 가장 최적이라고 생각되는 것을 선택해 나가는 방식
• 이번 문제에서는 귤의 크기별 개수를 내림차순으로 정렬하여 가장 많은 개수를 우선적으로 선택함으로써 최소한의 종류로 k개의 귤을 얻는 방법을 사용했습니다.