문제

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

풀이 설계

귤 배열을 set 을 사용하여 중복을 제거한다.
for문을 이용하여 해당 크키가 몇개인지 count를 사용해서 숫자를 센다.
[크기, 개수]의 형태로 되어있는 배열을 lambda를 사용해 내림차순 정렬한다.
for문을 사용해 k가 0보다 작거나 같아질 때까지 answer+1 한다.

1차 시도 (실패)

시간초과가 발생했다.

def solution(k, tangerine):
    answer = 0
    dedupe = list(set(tangerine))
    tan_cnt = []
    for size in dedupe:
        tan_cnt.append([size, tangerine.count(size)])
    tan_cnt.sort(key=lambda x:x[1], reverse=True)
    for i in tan_cnt:
        k -= i[1]
        answer+=1
        if k<= 0: break
    return answer

2차 시도 (실패)

혹시나 count가 시간이 많이 걸리는 이유인가 해서 for문으로 직접 셋더니 더 많은 시간이 걸렸다...

def solution(k, tangerine):
    answer = 0
    dedupe = list(set(tangerine))
    tan_cnt = []
    for size in dedupe:
        cnt = 0
        for i in tangerine:
            if size == i:
                cnt += 1
        tan_cnt.append([size, cnt])
    tan_cnt.sort(key=lambda x:x[1], reverse=True)
    for i in tan_cnt:
        k -= i[1]
        answer+=1
        if k<= 0: break
    return answer

3차 시도 (성공)

리스트에서 벗어나서 딕셔너리를 사용해봤다.

def solution(k, tangerine):
    answer = 0
    tan_dict = {}
    for size in tangerine:
        if size in tan_dict:
            tan_dict[size] += 1
        else:
            tan_dict[size] = 1
    sort_value = sorted(tan_dict.values(), reverse=True)
    for value in sort_value:
        k -= value
        answer+=1
        if k<= 0: break
    return answer

다른 풀이

Counter를 사용해서 쉽게 푸는 방법이 있어서 적용해봤다.

import collections

def solution(k, tangerine):
    answer = 0
    tan_dict = collections.Counter(tangerine)
    sort_value = sorted(tan_dict.values(), reverse=True)
    for value in sort_value:
        k -= value
        answer+=1
        if k<= 0: break
    return answer

후기

리스트를 편하게 써와서 그런가 딕셔너리에 손이 안가서 매번 리스트로 만 풀었는데 딕셔너리도 시도 해봐야겠다...
Counter는 사기다...??, 코드도 짧아지고 시간도 빨라짐...
내장함수를 좀 더 공부해보면 도움이 될 것 같다.

티스토리

[프로그래머스] 귤 고르기 - 파이썬(python)