[Programmers/Python] - 귤 고르기

Programmers - 귤 고르기

---

문제

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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

입출력 예

k	tangerine	result
6	[1, 3, 2, 5, 4, 5, 2, 3]	3
4	[1, 3, 2, 5, 4, 5, 2, 3]	2
2	[1, 1, 1, 1, 2, 2, 2, 3]	1

입출력 예 설명

• 입출력 예 #1
  본문에서 설명한 예시입니다.

• 입출력 예 #2
  경화는 크기가 2인 귤 2개와 3인 귤 2개 또는 2인 귤 2개와 5인 귤 2개 또는 3인 귤 2개와 5인 귤 2개로 귤을 판매할 수 있습니다. 이때의 크기 종류는 2가지로 이 값이 최소가 됩니다.

• 입출력 예 #3
  경화는 크기가 1인 귤 2개를 판매하거나 2인 귤 2개를 판매할 수 있습니다. 이때의 크기 종류는 1가지로, 이 값이 최소가 됩니다.

---

풀이

설계

'서로 다른 종류'를 최소로 만들어야 하므로 크기가 동일한 귤을 그룹으로 묶어 그룹의 크기가 가장 큰 귤부터 상자에 담고 상자에 담긴 귤의 개수가 k개를 넘어서는 순간의 '종류의 수'를 반환하면 된다.

collections 라이브러리의 Counter는 중복된 원소가 담긴 배열을 입력으로 받으면 해당 배열과 등장 횟수를 딕셔너리 형태로 반환한다.

from collections import Counter

tangerine = [1, 3, 2, 5, 4, 5, 2, 3]
Counter(tangerine)

>>> Counter({1: 1, 3: 2, 2: 2, 5: 2, 4: 1})

또한 Counter의 .most_common() 메서드를 사용하면 가장 많이 등장한 원소부터 차례로 (원소, 등장 횟수)의 튜플이 반환된다.

from collections import Counter

tangerine = [1, 3, 2, 5, 4, 5, 2, 3]
Counter(tangerine).most_common()

>>> [(3, 2), (2, 2), (5, 2), (1, 1), (4, 1)]

이를 이용해 귤을 '가장 많이 등장한' 순서대로 정렬한 후, 각 귤의 등장 횟수(즉, 종류별 귤의 개수)를 상자에 담는 귤의 개수로 추가하여 k와 비교한다. 동시에 귤의 종류가 추가될 때마다 answer를 1씩 증가시킨다. 그리고 상자에 담은 귤의 개수가 k보다 크거나 같아지는 순간 반복문을 종료하고 answer를 반환하면 된다.

코드

from collections import Counter

def solution(k, tangerine):
    tangerine_sorted = Counter(tangerine).most_common()
    total_count = 0
    answer = 0
    for size, count in tangerine_sorted:
        total_count += count
        answer += 1
        if total_count >= k:
            break
    return answer