[프로그래머스] JS 알고리즘 - 귤 고르기

오늘은 프로그래머스에서 귤 고르기 문제를 풀었습니다.

다른 블로그를 보니 2단계치고는 쉬운 문제라고 하지만 그래도 나름 까다로운 편에 속하지 않았나 생각해요.

시간 복잡도를 줄이기 위해 많은 시도를 해보았던 것 같습니다.

 

 

 

 

 

문제 설명

 

[문제]

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

 

 

 

 

알고리즘 아이디어

 

처음에는 객체로 키-값을 저장하고, 배열로 그 키-값들을 그대로 바꿔서 Object.entries()로 정렬하려고 했습니다. 하지만 어차피 내림차순으로 정렬할 거기 때문에 값만 다시 정렬하면 되었습니다.

 

Object.entries()

Object.entries()는 객체의 각 키-값 쌍을 배열로 변환합니다. 이 함수는 객체를 [키, 값] 쌍을 포함하는 배열의 배열로 변환합니다. 예를 들어, 객체 { a: 1, b: 2 }는 Object.entries()에 의해 [['a', 1], ['b', 2]]로 변환됩니다.

 

 

이후 제가 선택한 개수들의 합을 제가 담으려고 하는 귤의 개수인 k에서 빼서 0이 될 때까지 반복하면 귤을 고르는 종류의 수를 구할 수 있습니다.

 

 

 

 

 

코드 구현과 이해

 

위 문제의 모범 답안은 아래와 같습니다.

제가 푼 방식이 아니라 검색으로 알게 된 방법인데, 아래 방법이 제가 가장 직관적으로 이해하기 쉬웠습니다.

 

 

 

예시 답안 1

function solution(k, tangerine) {
    const freq = new Map();
    
    for(let i = 0; i < tangerine.length; i++) {
        const target = freq.get(tangerine[i]);
        freq.set(tangerine[i], target ? target + 1 : 1);
    }
    //console.log(Array.from(freq.values()))

    const val = Array.from(freq.values()).sort((a, b) => b - a);
    let count = 0;

    //console.log(val)
    
    for(let i = 0; i < val.length; i++) {
        if (k <= 0) break;
        //console.log(`k: ${k}, val[i]: ${val[i]}`)
        k -= val[i];
        //console.log(`after k -= val[i]: ${k}`)
        count++;
    }

    return count;
}

 

 

val 배열의 각 요소를 확인하면서, k가 0 이하가 될 때까지 반복하게 됩니다.

이 과정을 거치면서 귤을 고르는 종류의 수를 구할 수 있습니다.

 

참고로 아래와 같은 방식으로 풀어보았지만 시간 초과 오류를 해결하지 못했습니다. 지금 생각해보니 console.log를 제거해 볼 생각을 하지 않았던 것 같습니다. 아래 코드에는 제가 디버깅했던 부분은 제외되어 있습니다.

 

 

 

 

예시답안 2

 

function solution(tangerine, k) {
    // 귤의 크기별 개수를 계산
    let sizeCount = {};
    tangerine.forEach(size => {
        sizeCount[size] = (sizeCount[size] || 0) + 1;
    });

    // 귤의 크기별 개수를 개수가 많은 순으로 정렬
    let sortedSizes = Object.entries(sizeCount).sort((a, b) => b[1] - a[1]);

    // k개의 귤을 선택할 때까지 다양한 크기의 귤을 선택
    let selected = 0;
    let types = 0;
    for (let [size, count] of sortedSizes) {
        if (selected + count <= k) {
            selected += count;
            types++;
        } else {
            // 필요한 귤의 수(k)를 초과하지 않도록 조정
            let remaining = k - selected;
            if (remaining > 0) {
                types++;
            }
            break;
        }
    }

    return types;
}

 

귤의 크기별로 개수를 계산하는 방식으로 접근합니다. 그리고 이를 크기별 개수가 많은 순으로 정렬합니다.

k개의 귤을 선택할 때까지 다양한 크기의 귤을 선택하게 됩니다. 선택된 귤의 개수가 k를 초과하지 않도록 조정하며, 필요한 귤의 수(k)에 도달할 때까지 이 과정을 반복합니다.

 

 

 

이런 알고리즘 문제의 핵심은 자바스크립트에서 Map과 Array를 필요에 맞게 잘 사용하는 것과, 그에 따른 문법을 정확히 숙지하는 것이라고 생각합니다.