프로그래머스 Level2 귤 고르기 Python

문제 링크

풀이

딕셔너리를 사용해서 해당 종류의 귤의 개수를 저장한다.

딕셔너리에 저장된 개수를 이용해 내림차순으로 배열을 정렬한다.

k개 만큼 담을때까지 계속 담고 담긴 종류의 개수를 리턴한다.

 

제한사항

• 1 ≤ k ≤ tangerine의 길이 ≤ 100,000
• 1 ≤ tangerine의 원소 ≤ 10,000,000

정답 코드

def solution(k, tangerine):
    answer = 0
    dic = {}
    arr = []
    for item in tangerine:
        if item in dic:
            dic[item] +=1
        else:
            dic[item] = 1
            arr.append(item)
    arr.sort(key=lambda x : -dic[x])
    cnt = 0
    for i in range(len(arr)):
        if cnt + dic[arr[i]] < k:
            cnt += dic[arr[i]]
            answer+=1
        else:
            if cnt < k:
                return answer+1
            else:
                return answer
    return answer

 

풀이 설명

간단한 그리디 문제 입니다.

내림차순으로 정렬한뒤 귤을 k개 만큼 선택할때 까지 종류의 개수를 구하는 문제입니다.