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

https://school.programmers.co.kr/learn/courses/30/lessons/138476

프로그래머스

나의 풀이 - 시간초과

def solution(k, tangerine):
    answer = 0
    clSum = 0
    cntList = []
    for st in list(set(tangerine)):
        cntList.append(tangerine.count(st))
    cntList.sort(reverse=True)
    for cl in cntList:
        clSum += cl
        answer += 1
        if k <= clSum:
            return answer
    return answer

def solution(k, tangerine):
    answer = 0
    clSum = 0
    cntList = []
    for st in set(tangerine):
        cntList.append(tangerine.count(st))
    cntList.sort()
    while True:
        clSum += cntList.pop()
        answer += 1
        if k <= clSum:
            return answer
    return answer

• count 함수를 이용해 푸니 시간초과가 났다.

나의 풀이 - 다른 사람 풀이 참조

from collections import Counter

def solution(k, tangerine):
    answer = 0
    sum = 0
    ct = Counter(tangerine)
    ct = ct.most_common()
    for c in ct:
        sum += c[1]
        answer += 1
        if k <= sum:
            return answer
    return answer

• 시간을 도저히 어떻게 줄여야 할지 모르겠어서 결국 검색을 했다.
• Counter 함수라는 것이 있는지 처음 알았다.
• Dictionary의 키,값을 뽑아 사용하는것이 O(n) 이라 시간복잡도가 낮다고 한다.