문제

---

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

입출력 예 설명

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

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

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

🔍 나의 코드1 - Counter 이용

---

from collections import Counter
def solution(k, tangerine):
    # 요소의 개수가 많은 순서대로 정렬
    counter = Counter(tangerine).most_common()

    total=0
    answer = 0

    for i in counter:
        total += i[1] # 귤의 개수를 더한다.
        answer += 1 # 귤의 종류를 더한다.
        if total >= k: # 필요한 귤의 개수보다 많거나 같다면 
            break

    return answer

코드 풀이

# 입력
6
1, 3, 2, 5, 4, 5, 2, 3

우선 Counter의 most_common()을 이용하여 요소의 개수가 많은 순서대로 정렬해주었다. (귤의크기:개수)

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

필요한 귤의 개수는 k개(6개)이므로 귤의 개수가 많은 순서대로 더하여 그 수가 k보다 크거나 같아지면 된다.

이때 귤의 크기 종류도 함께 세어주면 서로 다른 종류의 수의 최솟값을 구할 수 있다.

참고) Counter의 사용법

코드1 - 더 나은 코드

---

from collections import Counter
def solution(k, tangerine):

    answer = 0

    counter = Counter(tangerine) # 개수 세기

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

    return answer

달라진 점

• {귤사이즈:개수}에서 key값은 필요가 없으므로 value만 받아오면 된다.
• 귤의 개수를 저장하는 변수 total을 만들 필요없이 있는 변수 k를 활용한다. 변수k에서 귤의개수를 빼주고 k가 0이하가 되면 for문을 탈출한다.

🔍 나의 코드2 - dictionary 이용

---

def solution(k, tangerine):
    answer = 0

    # 딕셔너리 생성 (귤사이즈 : 개수)
    dic = {size:0 for size in tangerine} 

    # 개수 세기
    for i in tangerine:
        if i in dic:
            dic[i] += 1
        else:
            dic[i] = 1

    # 귤의 개수를 기준으로 내림차순 정렬
    dic_sorted = sorted(dic.items(), key=lambda x : x[1], reverse=True)

    total = 0
    for x,y in dic_sorted:
        total += y
        answer += 1
        if total >= k:
            break


    return answer

Comment

가장 많은 요소의 수를 세어야 한다는 점에서 이전에 풀었던 문제(숫자 카드2)와 비슷해서 Counter를 사용하는 알고리즘은 쉽게 떠올렸지만 Counter의 사용법을 잘 몰라서 검색하느라 시간이 걸렸다ㅜ
Counter의 사용법을 기억하자.