프로그래머스 Lv.2 | Python | 귤 고르기

1. 문제 정보

프로그래머스

• 난이도: Lv.2

---

2. 문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.
예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.
경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

제한 조건

• 1 ≤ k ≤ tangerine의 길이 ≤ 100,000
• 1 ≤ tangerine의 원소 ≤ 10,000,000

---

3. 접근 기준

이 문제는 “많이 등장하는 것부터 선택하는 게 유리한가?”를 판단해야 한다.

결론은 다음이다.

• 한 종류에서 많이 가져올수록 전체 종류 수가 줄어든다.
• 따라서 개수가 많은 귤부터 선택해야 한다.

빈도 기준 정렬 + 그리디 선택

---

4. 사용한 패턴 / 알고리즘

해시 (Counter / Dictionary)

• 귤 크기별 개수 카운트

그리디 (Greedy)

• 개수가 많은 것부터 선택

---

5. 핵심 아이디어

1. 귤 크기별 개수를 센다.
2. 개수가 많은 순서로 정렬한다.
3. 앞에서부터 하나씩 선택하면서 k를 줄인다.
4. k가 0 이하가 되는 순간 종료

---

6. 풀이 코드

from collections import defaultdict

def solution(k, tangerine):
    answer = 0

    # 직접 딕셔너리로도 카운트 (위 Counter와 동일한 역할)
    _dict = defaultdict(int)
    for i in tangerine:
        _dict[i] += 1

    # 개수만 추출해서 내림차순 정렬
    _dict = sorted(_dict.values(), reverse=True)

    # 개수가 많은 순서대로 k를 채움
    for val in _dict:
        if k <= 0:
            break  # 이미 k개 이상 확보했으면 종료
        
        k -= val      # 해당 크기의 귤을 모두 사용
        answer += 1   # 사용한 귤 종류 수 증가

    return answer

---

7. 핵심 로직 요약

이 문제의 핵심은 많이 등장하는 귤부터 선택해서 종류 수를 최소화하는 것이다.

• 귤 크기별 개수를 센다.
• 개수 기준으로 내림차순 정렬한다.
• 앞에서부터 k를 채운다.
• 필요한 최소 종류 수를 센다.

결국, “빈도 계산 + 내림차순 정렬 + 큰 것부터 선택” 이 흐름이 핵심이다.

---

8. 정리

처음 보면 “k개만 고르면 되니까 아무거나 골라도 되지 않나?”라는 생각이 든다.
근데 실제로는 종류 수를 최소화해야 한다는 조건 때문에 기준이 바뀐다.

여기서 중요한 포인트는 하나였다.

• 많이 있는 걸 먼저 쓰는 게 무조건 유리하다

이걸 못 잡으면 조합을 고민하게 되고, 잡으면 그냥 정렬 한 번으로 끝난다.

결국 이 문제는 복잡하게 생각할 필요 없이, “개수 많은 것부터 쓰는 게 이득인가?”만 판단하면 되는 문제였다.