[JS] 귤 고르기

 

 

 

난이되: Lv.2

문제: https://school.programmers.co.kr/learn/courses/30/lessons/138476#qna

프로그래머스

 

 

알고리즘

1. Map이나 Object로 무게별 귤 개수를 센다.

2. 개수를 기준으로 내림차순 정렬한다.

3. 한 상자에 담으려는 귤 개수인 k개가 될 때까지 2.의 맨 앞부터 더한다. 몇 번 더했는지가 귤 크기의 종류 수이므로 이 문제의 정답이 된다.

 

 

코드

Map으로 구현

function solution(k, tangerine) {
    var answer = 0;
    let sum = 0;
    const hashMap = new Map();

    for (t of tangerine) {
        if (!hashMap.has(t)) { hashMap.set(t, 1); }
        else {
            const num = hashMap.get(t) + 1;
            hashMap.set(t, num);
        }
    }

    const tangerineAmount = Array.from(hashMap.values());
    tangerineAmount.sort((a, b) => b - a);

    for (amount of tangerineAmount) {
        answer++;
        sum += amount;
        if (sum >= k) { return answer; }
    }

    return answer;
}

Object로 구현

function solution(k, tangerine) {
    var answer = 0;
    let sum = 0;
    const tangerineObj = Object();

    for (t of tangerine) {
        if (!tangerineObj[t]) { tangerineObj[t] = 1; }
        else { tangerineObj[t]++; }
    }

    const tangerineAmount = Object.values(tangerineObj).sort((a, b) => b - a);
    for (amount of tangerineAmount) {
        answer++;
        sum += amount;
        if (sum >= k) { return answer; }
    }

    return answer;
}

 

 

주저리

우선순위큐로 풀어야겠다는 생각은 했는데 자바스크립트에는 우선순위큐가 없다는 단점이 있다. 그럼 내가 구현해야 되는데 그게 너무 귀찮고 실제로 코테 치러 가서 우선순위큐 구현은 못할 거 같았다. 그래서 Object나 해시맵으로 풀어야 되는데 나는 해시맵 다루는 게 더 편하기도 하고 더 빠른 거 같아서 처음에는 해시맵으로 풀었다. 다 풀고 질문하기 들어가 봤는데 다들 Object로 푼 거 같아서 Object로도 풀어봤다. 테스트 케이스 돌려보니까 10번까지는 Object가 빠르고 중간엔 비슷하고 25번 정도부터는 해시맵이 빠르다. 귤 먹고 싶다.