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

문제링크

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

프로그래머스

접근방법

먼저 시간복잡도를 생각해보았다

100,000 10^5 이면  O(n^2)으로는 문제를 풀 수 없다.

흠..그렇다면 N이나 nlog(n)으로 문제를 풀어야 겠다.

입출력 예시를 봐보자.

보아하니 가장 종류가 많은것부터 순서대로 뽑아서 내가 원하는 값(k)가 되면된다.

풀이 구상:

파이썬의 딕셔너리로 해당크기의 갯수를 적어두고 value값을 기준으로 sorted한 다음 위에서부터 K값을 빼고

혹시나 K가 0이나 그 이하가 된다면 그게 result

 

def solution(k, tangerine):
    answer = 0
    memo = {}
    # 전부 돌아서 memo에 적어준다
    for i in tangerine:
        if i not in memo:
            memo[i] = 1
        else:
            memo[i] += 1
    # value값을 기준으로 sorted해준다
    result_dic = sorted(memo.items(), key = lambda  item : item[1], reverse = True)
    for i in result_dic:
        answer += 1
        k -= i[1]
        if k <= 0:
            break
    return answer

sorted해주는 부분이 낯설었다.

문제 접근은 비교적 쉬운 문제였다!