작성일 : 2024.11.26

귤 고르기 문제

문제 설명

과수원에서 수확한 귤을 크기별로 분류하여 k개를 선택하려 합니다. 이때 선택한 귤의 크기 종류가 최소가 되도록 해야 합니다.

예시

귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3]이고, k=6인 경우:

• 크기별 개수: 1(1개), 2(2개), 3(2개), 4(1개), 5(2개)
• 최적의 선택: 2, 3, 5 크기의 귤 선택 (총 6개, 3가지 크기)

제한 조건

1. k (선택할 귤의 개수)

   • 범위: 1 ≤ k ≤ tangerine 배열 길이 ≤ 100,000

2. tangerine 배열

   • 원소 범위: 1 ≤ 원소 ≤ 10,000,000
   • 각 원소는 귤의 크기를 나타냄

해결 코드

function solution(k, tangerine) {
  let answer = 0;
  const counts = new Map();

  for (const size of tangerine) {
    counts.set(size, (counts.get(size) || 0) + 1);
  }
  let sort = [...counts.values()].sort((a, b) => b - a);
  if (sort[0] >= k) return 1;
  for (const t of sort) {
    answer++;
    if (k > t) k = k - t;
    else break;
  }
  return answer;
}

알고리즘 설명

1. 크기별 귤 개수 세기

   • Map을 사용하여 각 크기별 귤의 개수를 저장
   • key: 귤의 크기
   • value: 해당 크기의 귤 개수

2. 개수 기준 정렬

   • Map의 values만 추출하여 배열로 변환
   • 내림차순 정렬 (많은 것부터 적은 순)

3. 최소 종류 계산

   • 가장 많은 크기의 귤부터 선택
   • 선택할 때마다 k에서 해당 개수를 차감
   • k가 0이 되면 종료

핵심 문법 요소

1. Map 객체 활용

// 맵 요소 저장
counts.set(size, value);

// 맵 값 가져오기 (없으면 0)
counts.get(size) || 0;

2. Map values를 배열로 변환

[...counts.values()];

3. 내림차순 정렬

sort((a, b) => b - a);

시간 복잡도

• O(n log n): 정렬이 지배적
• n은 서로 다른 귤 크기의 수

공간 복잡도

• O(n): Map 객체 사용
• n은 서로 다른 귤 크기의 수

Map 객체 주요 메서드

1. set(key, value): 맵에 key-value 쌍 저장
2. get(key): key에 해당하는 value 반환
3. values(): 맵의 모든 value를 반환
4. keys(): 맵의 모든 key를 반환
5. has(key): key 존재 여부 확인