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

프로그래머스의 레벨 2 문제 귤 고르기입니다.

문제 요구 조건

k개의 귤을 선택할 때 서로 다른 종류의 수를 최소화하는 것입니다. 서로 다른 종류의 수를 최소화하기 위해서 동일한 종류의 귤이 많은 순서대로 선택하면 풀 수 있습니다.

내 풀이 방법

1. 동일한 종류의 귤이 많은 순서를 알기 위해서 귤 배열을 순회하면서 딕셔너리에 키를 종류로, 갯수를 값으로 저장합니다.
2. 딕셔너리를 값을 기준으로 정렬하고 순회합니다. 이때, k -= value, answer += 1는 귤 1종류를 추가하는 것이고, k가 0이하라면 다 추가한 것이니 answer를 리턴합니다.

# 1. 가장 많이 등장한 순서대로 정렬
# 2. k개만큼 세면서 종류 몇가진지 체크

def solution(k, tangerine):
    answer = 0
    d = {}
    for tan in tangerine:
        d[tan] = d.get(tan, 0)
        d[tan] += 1
    for key, value in sorted(d.items(), key=lambda x: -x[1]):
        k -= value
        answer += 1
        if k <= 0:
            break
    return answer

저는 대부분의 알고리즘 문제를 풀 때, 어림잡아 1억번 이하의 반복으로 해결하려고 합니다. k와 귤 배열 길이의 범위가 [1, 100000] 이고, 귤 종류의 범위가 [1, 10000000]이므로 풀이의 1번을 해결하는데 O(n)이고, 2번을 해결하는데 정렬에 O(nlogn)이고 귤 종류를 추가하는데 O(n)이므로 1억번 이하에 충분히 가능하다고 생각했습니다.

다른 사람의 풀이법

여러가지 방법이 있었지만 눈에 띈 방법은 아래와 같습니다.

1. collections 모듈을 활용해서 코드 단축하기