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

📃 문제

💟 코드

첫번째 풀이에서 시간초과가 발생해서 고민끝에 counter를 활용해 문제를 해결했다.

첫번째 코드

def solution(k, tangerine):
    answer = 0
    set_val = list(set(tangerine))
    lst = [0] * len(set_val)
    for i in range(len(set_val)):
        lst[i] = tangerine.count(set_val[i])
    sort_val = sorted(lst, reverse=True)
    cnt = 0
    for i in sort_val:
        if cnt < k:
            cnt += i
            answer += 1
        else: break
    return answer

해당 코드에서는 tangerine.count() 함수가 리스트 전체를 매번 순회하면서 개수를 세기 때문에, 리스트의 크기가 커질수록 시간이 오래걸린다는 문제가 있었다.

두번째 코드

from collections import Counter

def solution(k, tangerine):
    # 귤 크기별로 개수를 센다
    count = Counter(tangerine)
    # 개수를 내림차순으로 정렬한다
    sorted_count = sorted(count.values(), reverse=True)
    answer = 0
    cnt = 0
    # 크기별로 많이 포함된 귤부터 차례대로 더해간다
    for i in sorted_count:
        if cnt < k:
            cnt += i
            answer += 1
        else: break
    return answer

counter 함수를 활용해 귤 크기별 개수를 쉽게 계산해놓을 수 있었고, 그로 인해 시간을 줄일 수 있었다!

✨ 코드 풀이

귤 크기의 종류를 최소화 하여 상자를 채워야 했기 때문에 같은 크기 당 갯수가 가장 많은 귤로 상자를 채워야 했다.
때문에 먼저 귤 크기별로 개수를 세었고, 개수를 내림차순으로 정렬했다.
그 후 앞에서부터 k보다 크거나 같을 때 까지 개수를 더해갔고, 더할 때마다 answer에 1씩 더해줌으로써 귤 종류의 개수를 셀 수 있었다!