[프로그래머스]귤 고르기

문제출처
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

입출력 예

문제풀이

1. 중복갯수를 셀수 있는 함수를 만들어준다.
2. 함수에 배열을 넣어 중복갯수를 리턴하여 각 값만 배열에 담아준다.
3. 배열을 내림차순 정렬을 해준다.
4. 각 배열을 돌면서 각 값만큼 k에서 빼주고 answer은 하나씩 더해준다.
5. k가 0보다 작거나 같으면 멈춰준다.

코드 1차시도

function solution(k, tangerine) {
    var answer = 0;
    let getElCount = (arr) => arr.reduce((acc, cur) => ({ ...acc, [cur]: (acc[cur] || 0) + 1 }), {});
    let values = Object.values(getElCount(tangerine));
    values.sort((a,b) => b-a);
    
    for(let el of values){
        k -= el;
        answer++;
        if(k<= 0) break;
    }
    return answer;
}

이렇게 했는데 시간초과가 떠서 마지막 반복문을 도는 게 문제일 거 같아 이진탐색으로 변경하였다. 그래도 시간초과가 떳다ㅠㅠㅠ😥

코드 2차시도

function solution(k, tangerine) {
    var answer = 0;
     let getElCount = (arr) => arr.reduce((acc, cur) => ({ ...acc, [cur]: (acc[cur] || 0) + 1 }), {});
    let values = Object.values(getElCount(tangerine));
    values.sort((a,b) => b-a);
   
    for(let i=1; i<values.length; i++){
        values[i] += values[i-1];
    }
    
    if(values[0] >= k) return 1;
    let start = 1;
    let end = values.length-1; 
    let middle ;
    while(start <= end){
        middle = parseInt((start+end)/2);
        
        if(values[middle] >= k && values[middle-1] < k) return middle+1;
        else{
          if(values[middle] >= k) end = middle -1;
            else start = middle + 1;
        }
    }
}

혹시나 하는 마음에 reduce를 사용한 함수를 빼고 배열을 돌면서 key에 맞는 누적값을 object에 넣어주었는데 드디어 통과되었다..!

코드 3차시도

function solution(k, tangerine) {
    var answer = 0;
    let getElCount = {};
    for(let el of tangerine){
        getElCount[el] = (getElCount[el] || 0) +1;
    }
    
    let values = Object.values(getElCount);
    values.sort((a,b) => b-a);
    
    for(let el of values){
        k -= el;
        answer++;
        if(k<= 0) break;
    }
    
    return answer;
   
}

다른사람 코드

function solution(k, tangerine) {
  let answer = 0;
  const tDict = {};
  tangerine.forEach((t) => tDict[t] = (tDict[t] || 0) + 1);
  const tArr = Object.values(tDict).sort((a, b) => b - a);
  for (const t of tArr) {
    answer++;
    if (k > t) k -= t;
    else break;
  }
  return answer;
}

비슷한 방법인데 forEach를 사용해서 더 깔끔하게 코드가 작성되었다.