[PS, Algorithm] - 귤 고르기 (코딩테스트 연습, LEVEL 2)

📒문제

📌풀이

from collections import Counter

def solution(k, tangerine):
    data = Counter(tangerine).most_common()

    result, tmp = 0, k
    for d in data:
        if tmp <= 0:
            return result
        else:
            tmp -= d[1]
            result += 1
            
    return result
    

저번에 알게 된 most_common()함수를 이용해서 counter(dict형에 포함된다)의 정보를 개수가 많은 순서대로 정렬해 주었다.

우리는 종류에 상관없이, 어떤 제약조건도 없이 단지 k개를 채우기만 하면 되므로, 최대한 많은 수의 귤부터 먼저 골라준다면 최소 종류만으로 k개를 채울 수 있다. 아주 간단한 그리디 문제다.

그리디 문제를 맞닥뜨리면 항상 조금 꼬아서 어렵게 생각하는 경향이 있는 것 같다. 실제 코딩테스트에 나오는 그리디 문제들도 구현이나 아이디어 자체가 그리 어렵지는 않으니까 단순하게 생각하려고 노력하자...