문제설명
경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.
예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.
경화가 한 상자에 담으려는 귤의 개수k와 귤의 크기를 담은 배열tangerine이 매개변수로 주어집니다. 경화가 귤k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 1 ≤
k≤tangerine의 길이 ≤ 100,000- 1 ≤
tangerine의 원소 ≤ 10,000,000
입출력 예
k tangerine result 6 [1, 3, 2, 5, 4, 5, 2, 3] 3 4 [1, 3, 2, 5, 4, 5, 2, 3] 2 2 [1, 1, 1, 1, 2, 2, 2, 3] 1
내 풀이
function solution(k, t) {
let answer = 0;
const map = new Map();
for(let i=0; i<t.length; i++){
map.set(t[i], (map.get(t[i]) || 0) + 1)
}
const arr = [...map].sort((a,b)=>b[1]-a[1])
for(const [_, val] of arr){
answer++
if(k > val) k -= val;
else return answer
}
}서로 다른 종류의 수를 최소화 해야한다.
즉, 개수가 많은것부터 더하던가 빼던가 하면서 답을 구하면 되는데
처음에는 그냥 중복제거하면 되겠구나 했는데 중복제거는 아무 소용 없었다.
그래서 생각한게 2차원 배열 이였다.
[[귤 사이즈,개수]]
사이즈 마다 개수를 담고 있는 2차원 배열을 만들기 위해 map을 사용했다.
저번에 배운걸 써보고싶었다.
개수를 기준으로 내림차순으로 정렬해 주면 key(귤 사이즈)는 필요없으니
val(개수)만으로 계산해 준다.
더하면서 할거라면 sum이라는 변수를 따로 만들어야 하는데
빼면서 할거면 따로 변수를 만들 필요 없이 그냥 k에서 빼면 된다.
