Lv.2 : 귤 고르기 [JavaScript]

https://school.programmers.co.kr/learn/courses/30/lessons/138476

프로그래머스

---

문제 풀이 1 : Set 사용 => 실패 (시간초과) 

function solution(k, tangerine) {
    var idx = 0;
    var sum = 0;
    
    var setTangerine = new Set(tangerine);
    var tangerineCount = Array.from(setTangerine).map((e) => tangerine.filter((t) => t == e).length).sort((a, b) => b - a);
        
    while(k > 0){
        sum += tangerineCount[idx];
        idx++;
        if(sum >= k) break;

        
    }
    
    return idx;
}

귤 개수를 위한 배열을 만드는데 너무 많은 시간을 사용하는가 초과가 났다

set으로 바꾼 걸 배열로 바꿔서 filter에 sort까지 해서 그런가..

 

문제 풀이 2 : 객체

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

크기 별 개수를 가지는 tObj를 만들어, 객체의 값을 내림차순 정렬한 sortT 배열을 만들어 사용

가장 개수가 많은 귤부터 더해가며 k개를 넘으면 break

 

문제 풀이 3 : 2에서 sum 없이 계산

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

sum을 사용하지 않고, k개에서 귤 개수를 빼가면서 k개를 다 채울 때까지 계산도 가능