귤 고르기, level2, 프로그래머스, python

문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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
4	[1, 3, 2, 5, 4, 5, 2, 3]	2
2	[1, 1, 1, 1, 2, 2, 2, 3]	1
6	[1, 3, 2, 5, 4, 5, 2, 3]	3

---

입출력 예 설명

입출력 예 #1

• 본문에서 설명한 예시입니다.

입출력 예 #2

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

입출력 예 #3

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

 

 

문제풀이

각 사이즈에 해당하는 귤을 세어, 내림차순 정렬한 후 k개를 만들어주면 된다.  리스트 tangerine을 사용하여 귤 사이즈를 key값으로, 귤의 갯수가 value인 딕셔너리를 만들어 준다.

 

dic = {}
    
for num in tangerine:
    if num not in dic.keys():
        dic[num] = 1
    else:
        dic[num] += 1
        
dic = sorted(dic.items(), key=lambda x: x[1], reverse=True)

print(dic)

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

이 코드를 설명하자면 먼저 tangerine 리스트에 접근하여 각 원소를 딕셔너리의 key값으로 할당한다. 만약 딕셔너리에 해당 키 값이 없을 경우에는 새롭게 추가를 하고, 해당 키 값이 있다면 그 키 값에 해당하는 value 를 1씩 추가해 준다.

 

내림차순 정렬할 것이기 때문에 람다 함수를 사용하여 value 기준으로 정렬하면 다음과 같이 원소가  튜플 형태인 리스트를 얻을 수 있다.

 

마지막으로 이 리스트를 for문으로 돌아가며 k에서 value 값을 뺄 때마다 count를 한다(왜냐하면 빼는 단위가 귤의 종류 이므로).

for i in dic:
        k -= i[1]
        answer += 1
        if k <= 0:
            break

k값이 0보다 작거나 같으면 k만큼 귤의 크기를 담은 것이라 생각할 수 있으므로, for문을 종료하고 count한 귤의 갯수를 반환해준다.

 

 

완성코드

def solution(k, tangerine): 
    dic = {}
    answer = 0
    for num in tangerine:
        if num not in dic.keys():
            dic[num] = 1
        else:
            dic[num] += 1
    dic = sorted(dic.items(), key=lambda x: x[1], reverse=True)
    print(dic)
    
    for i in dic:
        k -= i[1]
        answer += 1
        if k <= 0:
            break
        
    return answer

풀이 시간이 오래걸리는 것으로 봐서는 효율성 고려를 조금 더 해주어야 할것 같다.