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

[84] 귤 고르기

책 구매하기

문제 정보

• 분류: 그리디
• 정답률: 66%
• 권장 시간 복잡도: O(N log N)
• 핵심 키워드: 빈도 정렬, 종류 최소화, Counter, 개수 누적
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/138476

문제를 읽을 때 체크할 포인트

k개를 만들되 종류 수를 최소화하려면 많이 있는 귤 종류부터 가져가야 한다. 빈도만 세고 큰 순서대로 누적하면 된다.

한 번의 선택 기준이 맞는지만 확인되면 그 뒤는 같은 규칙을 반복하면 된다. 결국 매 순간 무엇을 먼저 선택해야 전체가 가장 이득인지 보는 문제다.

풀이 흐름

1. 귤 크기별 개수를 Counter로 센다.
2. 개수만 모아 내림차순 정렬한다.
3. 앞에서부터 누적해 k 이상이 되는 순간 사용한 종류 수를 반환한다.

구현할 때 놓치기 쉬운 부분

귤의 개수 자체보다 크기별 빈도가 중요하다. 종류 수를 최소로 줄여야 하므로 많이 나온 크기부터 담아 가는 방향이 자연스럽다.

파이썬 정답 코드

from collections import Counter

def solution(k, tangerine):
  # 귤 크기별 개수를 Counter로 센다.
  counts = Counter(tangerine)
  sizes = sorted(counts.values(), reverse=True)

  total = 0
  # 개수만 모아 내림차순 정렬한다.
  for i, count in enumerate(sizes, 1):
    # 앞에서부터 누적해 k 이상이 되는 순간 사용한 종류 수를 반환한다.
    total += count
    if total >= k:
      return i

시간 복잡도

N은 tangerine의 길이이다.

핵심 비용은 정렬이다. N개 데이터를 정렬하는 데 O(N log N)이 들고, 정렬 뒤에 붙는 한 번의 순회나 해시 조회는 선형이라 전체 차수를 바꾸지 않는다.

따라서 시간 복잡도는 O(N log N)이다.