프로그래머스 : 귤 고르기 [lv.2, 구현, 파이썬 Counter 함수]

문제

프로그래머스

 

문제 설명 🍊

🤔 경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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가지로, 이 값이 최소가 됩니다.

 

생각한 풀이 방법

귤을 크기별로 분류
: 딕셔너리 활용하기 : 크기, 빈도수 (카운트로 저장) - 반복문 돌리며 확인 : 문자열로 바꾸고 count 함수 써서 몇 번씩 나오는 지 확인
 → k개로 맞추어서 내보내 최소 갯수 확인

서로 다른 종류의 수를 최소화
: 딕셔너리를 빈도수로 정렬한 후, 최소가 되는 조합을 찾아야함 → 어떻게? : 먼저 정렬, 큰 수가 많이 들어가면 최소가 되니까. 

 

 → Set() 함수를 사용해서 tangerine 리스트의 중복을 없애고 반복문을 실행, 딕셔너리를 사용해서 값을 구했더니 시간초과가 떴다. 

 → 찾아보니 Counter 함수를 사용해서 구하면 시간초과가 안뜨더라. Counter 함수의 존재를 처음 앎,, 

 

파이썬 collections 모듈의 Counter 사용법

 

Counter 기본 사용법

from collections import Counter

Counter 생성자는 여러 형태의 데이터를 인자로 받는데요.
먼저 중복된 데이터가 저장된 배열을 인자로 넘기면 각 원소가 몇 번씩 나오는지가 저장된 객체를 얻게 됩니다.

>>> Counter(["hi", "hey", "hi", "hi", "hello", "hey"]) Counter({'hi': 3, 'hey': 2, 'hello': 1})

Counter 생성자에 문자열을 인자로 넘기면 각 문자가 문자열에서 몇 번씩 나타나는지를 알려주는 객체가 반환됩니다.

>>> Counter("hello world") Counter({'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1})

 

[정답 코드]

from collections import Counter

def solution(k, tangerine):
    answer = 0 
    
    dic1 = dict(sorted(Counter(tangerine).items(), key=lambda x:x[1], reverse = True))
    
    count = 0
    for i in dic1.values():
        if (count>=k):
            break
        count+=i
        answer+=1
    return answer