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

문제

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.

경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

 

 

제한조건

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

 

 입출력 예

 

 

 

 

---

풀이

1. 이 문제는 tangerine 배열을 보고 각각의 귤의 크기가 얼마인지를 보고난 후,  크기를 최대한 비슷하게 해야 하므로 같은 크기의 귤이 몇개인지를 카운트 해준 다음에 크기가 같은 귤이 많은 순서로 k 개의 귤을 담는 문제이다.

2. 먼저 tangerine 배열에서 각 숫자가 몇번 중복되는지를 알아낸 후, 최대한 적은 종류로 k 개를 담아 낼 수 있도록 중복되는 수를 담은 배열을 내림차순으로 정렬해서 몇 종류를 담으면 되는지 출력하면 된다.

 

---

1. Counter를 이용하여 같은 크기가 몇번 중복되었는지 확인한다.

Counter([1, 3, 2, 5, 4, 5, 2, 3])는 {1: 1, 3: 2, 2: 2, 5: 2, 4: 1}를 반환

2. most_common을 이용하여 최빈값 순서로 정렬한다.

Counter(tangerine).most_common()은 [(3, 2), (2, 2), (5, 2), (1, 1), (4, 1)] 튜플을 정렬된 리스트로 반환

3. 그 후  k보다 크거나 같을 때 몇 종류의 귤이 담겼는지를 리턴해준다.

from collections import Counter

def solution(k, tangerine):
    answer = 0

    for c in Counter(tangerine).most_common():
        k -= c[1] 

        answer += 1

        if k <= 0:
            break

    return answer