[programmers] Lv2 귤 고르기 - Python

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

프로그래머스

 

 

 

<문제 풀이>

- 문제에서 구하고자 하는 것은 귤의 종류(크기)수를 최소화 하는 것이다. 즉, 해당 크기의 귤이 많은 순서대로 귤을 수확하여 k를 맞추면 된다는 것이다.

- 문제에서 주어진 입력값(확인해야할 귤)은 최대 100,000 이므로 O(NlogN)이내로 설계 하면 문제를 해결할 수 있다.

- 먼저, 종류(크기)별로 귤의 개수를 분류한 후, 반복문을 이용해 [귤 크기, 수]를 담은 리스트를 생성한다.

- 이후 귤의 개수가 많은 순서대로 해당 리스트를 정렬한다. Python sort의 시간 복잡도: O(NlogN)

- 반복문을 이용해 귤을 상자에 담으면서 종류를 카운트 한다. 이때 k개를 초과하면 종류를 return한다.

 

 

 

<Code>

from collections import defaultdict


def solution(k, tangerine):
    answer = 0
    tan_num = defaultdict(int)
    for i in tangerine:    # 종류별 귤 개수 세기
        tan_num[i] += 1

    arr = []
    for t in tan_num:    # 2차원 배열로 만들기 [귤 크기, 수]
        arr.append([t, tan_num[t]])

    arr.sort(key=lambda x: x[1], reverse=True)    # 귤 갯수가 많은 순으로 정렬

    for i in arr:
        answer += 1    # 종류 +1
        k -= i[1]    # 해당 크기의 개수 차감
        if k <= 0:    # 귤을 모두 고른 경우 종료
            return answer

※ 잘못된 점, 개선점 등이 있다면 언제든 댓글로 알려주시면 감사하겠습니다.