프로그래머스 - 귤 고르기 JS

문제

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.
경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

접근법

경화가 수확한 귤은 tangerine.length개 이고, 상자에 담으려는 귤은 k개
tangerine.length-k개를 버려서 크기가 서로 다른 종류의 수를 최소로 만들어줘야 함

그렇다면 여러 종류 중에서 그 개수가 가장 적은 것을 우선적으로 버리는 게 가장 유리
Ex)1 - 4개 2 - 3개 3 - 1개 4 - 1개
3개를 버릴 수 있다면 2개짜리를 모두 버리거나 or 3개와 4개까지를 버릴 수 있는데 후자가 더 최솟값이 나옴

사실 생각하는 건 쉬운데 조금 헷갈렸던 게
map 자료구조로 각각 몇개가 있는지는 구할 수 있는데, map을 정렬할 수는 없어서 개수가 가장 적은 것을 찾을 수는 없음

그래서 Array.from(map.entries()) -> [[1,4],[2,3],[3,1],[4,1]] 로 변경 후에

1번째 값을 기준으로 정렬 한 후, 버릴 수 있을 때까지 버려주면서 종류를 줄여나가면 됨

코드

function solution(k, tangerine) {
  //k랑 귤 수랑 똑같을수도 있음 - 이때는 못버림 
  let trash = tangerine.length - k
  if(!trash){
      return new Set(tangerine).size
  }
  //trash만큼 버릴 수 있음
  const map = new Map()
  for(let t of tangerine){
      map.set(t,(map.get(t) || 0) + 1)
  }
    //제일 적은 종류부터 버리기
  let size = map.size
  const arr = Array.from(map.entries())
  arr.sort((a,b) => a[1] - b[1])
  for(let n of arr){
      if(n[1] <= trash){
          size --
          trash -= n[1]
      }
  }
  return size
}