Lv.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

예제

나의 풀이

해당 숫자가 몇 번 등장하는지에 대한 딕셔너리를 만든 후, 딕셔너리 기준으로 오름차순 정렬하여 가장 많이 등장하는 숫자의 횟수를 k값에서 빼준다. 빼기가 일어날 때마다 숫자에 해당하는 사이즈가 박스에 담기는 것이므로 cnt += 1을 해준다. k의 값이 0 또는 음수가 될 때의 k 값이 정답이 된다.

def solution(k, tangerine):
    cnt = 0
    dic = {}
    for i in tangerine:
        if i not in dic:
            dic[i] = 1
        else:
            dic[i] += 1
            
    dic = sorted(dic.items(), key = lambda x: x[1])
    
    while k > 0:
        k -= dic.pop()[1]
        cnt += 1
    return cnt

다른 풀이

Counter()라는 내장 함수를 사용하면 쉽게 풀 수 있는 문제였다.

from collections import Counter
def solution(k, tangerine):
   answer = 0
   cnt = Counter(tangerine)

   for v in sorted(cnt.values(), reverse = True):
       k -= v
       answer += 1
       if k <= 0:
           break
   return answer

끄적끄적

Counter

Counter는 컬렉션 안에 있는 요소들의 개수를 세는데 특화된 함수형 클래스이다. 리스트, 문자열 등 반복 가능한 객체의 각 요소가 몇 번 나타나는지 세어준다.

from collections import Counter

data = ['apple', 'banana', 'apple', 'orange', 'banana', 'apple']
counter = Counter(data)

print(counter) # Counter({'apple': 3, 'banana': 2, 'orange': 1})

주요 메서드

1. most_common(n): 가장 많이 등장한 요소 n개를 리스트로 반환

print(c.most_common(2))
# [('apple', 3), ('banana', 2)]

2. elements(): 등장 횟수만큼 각 요소를 반복하는 이터레이터를 반환

print(list(c.elements()))
# ['apple', 'apple', 'apple', 'banana', 'banana', 'orange']

3. update(iterable or dict): 기존 카운터에 숫자를 추가

c.update(['banana', 'apple', 'grape'])
print(c)
# Counter({'apple': 4, 'banana': 3, 'orange': 1, 'grape': 1})

4. subtract(iterable or dict): 기존 카운터에 숫자를 제거, 음수도 가능

c.subtract(['apple', 'banana', 'banana', 'kiwi'])
print(c)
# Counter({'apple': 3, 'orange': 1, 'grape': 1, 'banana': 1, 'kiwi': -1})