경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.
경화가 한 상자에 담으려는 귤의 개수 k
와 귤의 크기를 담은 배열 tangerine
이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
k
≤ tangerine
의 길이 ≤ 100,000tangerine
의 원소 ≤ 10,000,000입출력 예 1
입출력 예 2
function solution(k, tangerine) {
let answer = 0;
const sizesMap = new Map();
for (let i = 0; i < tangerine.length; i++) {
const size = tangerine[i];
sizesMap.set(size, sizesMap.get(size) ? sizesMap.get(size) + 1 : 1);
}
const countsBySize = Array.from(sizesMap.values()).sort((a, b) => b - a);
for (let i = 0; i < countsBySize.length; i++) {
k -= countsBySize[i];
answer++;
if (k <= 0) {
break;
}
}
return answer;
}
만약 컨테이너 벨트의 맨 앞에 놓인 상자가 현재 트럭에 실어야 하는 순서가 아니라면 그 상자를 트럭에 실을 순서가 될 때까지 잠시 다른 곳에 보관해야 합니다. 하지만 고객의 물건을 함부로 땅에 둘 수 없어 보조 컨테이너 벨트를 추가로 설치하였습니다. 보조 컨테이너 벨트는 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있습니다(즉, 가장 마지막에 보조 컨테이너 벨트에 보관한 상자부터 꺼내게 됩니다). 보조 컨테이너 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못 한다면, 더 이상 상자를 싣지 않습니다.
예를 들어, 영재가 5개의 상자를 실어야 하며, 택배 기사님이 알려준 순서가 기존의 컨테이너 벨트에 네 번째, 세 번째, 첫 번째, 두 번째, 다섯 번째 놓인 택배상자 순서인 경우, 영재는 우선 첫 번째, 두 번째, 세 번째 상자를 보조 컨테이너 벨트에 보관합니다. 그 후 네 번째 상자를 트럭에 싣고 보조 컨테이너 벨트에서 세 번째 상자 빼서 트럭에싣습니다. 다음으로 첫 번째 상자를 실어야 하지만 보조 컨테이너 벨트에서는 두 번째 상자를, 기존의 컨테이너 벨트에는 다섯 번째 상자를 꺼낼 수 있기 때문에 더이상의 상자는 실을 수 없습니다. 따라서 트럭에는 2개의 상자만 실리게 됩니다.
택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order
가 주어졌을 때, 영재가 몇 개의 상자를 실을 수 있는지 return 하는 solution 함수를 완성하세요.
제한사항
order
의 길이 ≤ 1,000,000order
는 1이상 order의 길이 이하의 모든 정수가 한번씩 등장합니다.order[i]
는 기존의 컨테이너 벨트에 order[i]
번째 상자를 i+1번째로 트럭에 실어야 함을 의미합니다.function solution(order) {
let boxCount = 0;
const stack = [];
for (let i = 1; i <= order.length; i++) {
stack.push(i);
while(stack.length > 0 && order[boxCount] === stack[stack.length - 1]) {
stack.pop();
boxCount++;
}
}
return boxCount;
}