[Programmers] L2. 귤 고르기 (Greedy/Python)

---

[문제 링크] 👇

프로그래머스

---

풀이 방법

1️⃣ 귤의 종류별 개수 파악

• 귤의 크기별로 몇 개씩 있는 개수를 센다. (Counter() 함수 이용)

from collections import Counter
tangerine = [1, 3, 2, 3, 2, 4, 4, 4, 4]
print(Counter(tangerine))

• 출력 결과 : Counter({4: 4, 3: 2, 2: 2, 1: 1})

2️⃣ 개수를 기준으로 정렬

• 귤의 개수를 내림차순으로 정렬한다. 이는 개수가 많은 종류부터 선택하도록 하기 위함이다.
• 위 예시에서 내림차순으로 정렬하면 [(4, 4), (3, 2), (2, 2), (1, 1)] 이 된다.

3️⃣ 개수가 많은 종류부터 선택

• 개수가 많은 귤 종류부터 선택하여 k개 이상의 귤을 고르는 것이 최소 종류를 선택하는 방법이다.

4️⃣ 필요한 종류의 개수를 세기

• 개수가 많은 종류부터 선택하면서 k개 이상이 되는 시점에서 선택한 귤 종류의 개수를 반환한다.

Solution

from collections import Counter
def solution(k, tangerine):
    answer = 0
    tangerine = sorted(Counter(tangerine).items(), key=lambda x: x[1], reverse=True)
    for num, cnt in tangerine:
        if k > 0:
            k -= cnt
            answer += 1
        else: break
    return answer

 

시간 복잡도

• 귤의 개수를 세는 데 O(n) (n 은 귤 배열의 길이)
• 개수를 정렬하는 데 O(mlogm) (m 은 귤 종류의 개수)
• 종류를 탐색하며 k개를 고르는 데 최악의 경우 O(m)

따라서 전체 시간 복잡도는 O(n + mlogm) 이다.

 

---