프로그래머스 - 귤 고르기

✨ Lv. 2 - 귤 고르기

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/138476

문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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

---

풀이 코드 + 설명

우선 귤의 크기의 종류가 가장 작도록 해야하기 때문에 각 크기별로 몇 개의 귤이 있는지를 파악할 필요가 있습니다. 이를 위해 객체를 활용하였습니다. 빈 객체를 생성하여 tangerine을 순회하며, 각 크기를 key로 하여 개수를 저장합니다.

개수를 파악했으면, 개수가 가장 많은 순서대로 귤을 k개만큼 상자에 담으면 됩니다. 이때, k개보다 담은 개수가 많거나 같아지면 이제까지 총 몇 가지의 귤을 담았는지를 return 하면 됩니다. 이러한 순서대로 풀이한 코드는 아래와 같습니다.

function solution(k, tangerine) {
    const tangerineType = {};
    
    tangerine.forEach((t) => {
        if(tangerineType[t]) tangerineType[t]++;
        else tangerineType[t] = 1;
    })
    
    let sortable = [];
    
    for(let t in tangerineType) sortable.push([t, tangerineType[t]]);
    sortable.sort((a, b) => b[1] - a[1]);
    
    let result = 0;
    
    for(let i = 0; i < sortable.length; i++) {
        result++;
        if(k - sortable[i][1] <= 0) return result;
        else k -= sortable[i][1];
    }
}

해당 코드로도 해결은 가능하지만, 객체에 담고 정렬을 위해 이를 다시 빈 배열에 담는 과정이 비효율적입니다. 해당 방법 대신 Object.values를 사용하여 더 간결하게 코드를 작성할 수 있습니다. Object.values는 객체의 value만 담긴 배열을 return 합니다.

function solution(k, tangerine) {
    const tangerineType = {}; 
    
    tangerine.forEach((t) => tangerineType[t] = (tangerineType[t] || 0) + 1);  
    
    const sortedValue = Object.values(tangerineType).sort((a, b) => b - a);
    
    let result = 0;
    
    for(let i = 0; i < sortedValue.length; i++) {
        result++;
        if(k - sortedValue[i] <= 0) return result;
        else k -= sortedValue[i];
    }
}

---