[프로그래머스] 귤 고르기

문제 요약

귤 k개를 골라 한 상자에 담을 때, 상자에 포함되는 귤 크기의 종류 수를 최소화해야 한다.

같은 크기의 귤은 모두 같은 종류로 취급하며, 귤 전체 개수는 최대 100,000개다.

핵심 아이디어

한 종류를 선택했을 때 상자에 넣을 수 있는 귤 수는 그 크기의 전체 개수를 넘을 수 없다.

따라서 종류 수를 적게 사용하려면 한 종류에서 최대한 많은 귤을 가져와야 한다. 즉, 크기별 귤 개수를 세고 개수가 많은 순서대로 선택하면 된다.

풀이 과정

1. Counter로 크기별 귤 개수를 센다.
2. 빈도만 내림차순 정렬한다.
3. 가장 큰 빈도부터 누적한다.
4. 누적 개수가 k 이상이 되는 순간 선택한 종류 수를 반환한다.

Python 코드

from collections import Counter


def solution(k, tangerine):
    # 귤 크기별 개수를 센다.
    counts = Counter(tangerine)

    # 많이 존재하는 크기부터 선택한다.
    frequencies = sorted(counts.values(), reverse=True)

    selected_count = 0
    type_count = 0

    for frequency in frequencies:
        selected_count += frequency
        type_count += 1

        if selected_count >= k:
            return type_count

왜 가장 많은 종류부터 선택해야 할까?

어떤 선택에서 적게 남아 있는 크기를 선택했지만, 선택하지 않은 다른 크기의 귤 수가 더 많다고 하자. 두 크기를 교체하면 사용한 종류 수는 그대로이고, 상자에 담을 수 있는 귤 수는 줄어들지 않는다.

이 교체를 반복하면 항상 빈도가 큰 크기들부터 선택하는 형태로 바꿀 수 있다. 따라서 빈도 내림차순으로 선택해 처음 k개 이상을 채우는 순간의 종류 수가 최솟값이다.

정당성 증명

빈도 내림차순으로 정렬한 값을 f1 >= f2 >= ...라고 하자.

r개 종류를 사용해서 담을 수 있는 귤의 최대 개수는 f1 + f2 + ... + fr이다. 어떤 다른 r개 종류를 고르더라도, 각 순위에서 선택 가능한 빈도는 상위 r개 빈도를 넘을 수 없기 때문이다.

따라서 누적 빈도가 처음 k 이상이 되는 최소 인덱스 r보다 적은 종류 수로는 k개를 담을 수 없다. 반대로 상위 r개 종류를 선택하면 k개 이상을 담을 수 있다. 그러므로 알고리즘이 반환하는 r은 최소 종류 수다.

복잡도 분석

서로 다른 귤 크기 수를 D라고 하자.

• 빈도 계산: O(N)
• 빈도 정렬: O(D log D)
• 누적 순회: O(D)

전체 시간 복잡도는 O(N + D log D)이고, 공간 복잡도는 O(D)이다.

주의할 점

• 마지막으로 선택한 크기에서 필요한 수보다 많은 귤이 있어도 괜찮다. 해당 크기의 귤 중 필요한 개수만 골라 담으면 된다.
• 귤의 실제 크기 범위가 크므로, 크기를 인덱스로 사용하는 배열보다 Counter 또는 딕셔너리로 빈도를 세는 방식이 자연스럽다.
• k가 전체 귤 수와 같다면 모든 등장 크기를 선택하게 된다.

마무리

이 문제는 "적은 종류로 많은 귤을 채운다"는 목표를 빈도 기준으로 바꾸면 간단해진다. 크기별 개수를 세고, 가장 많은 크기부터 선택하는 그리디 전략으로 최소 종류 수를 구할 수 있다.