[LeetCode] Reduce Array Size to The Half

문제링크

Reduce Array Size to The Half - LeetCode

 

배열이 주어질때 해당 배열의 유일한 요소 ( [3,3,3,3,3,4,4,4,5,5] ==> [3, 4, 5] )를 구하고
원본 배열에서 유일한 요소와 같은 요소를 제거할 경우
제거한 배열이 원본 배열의 크기의 절반보다 작아질 때 제거한 유일한 요소의 개수를 구하는 문제이다. (유일한 요소는 최소로 제거해야한다.)

접근 방법

주어진 원본 배열의 요소를 같은 요소가 많은 순서로 정렬하고 많은 요소부터 지우면 해결 가능할 듯 했다.
(ex => [5, 5, 3, 2, 6, 3, 3, 1, 3]을 [3, 3, 3, 3, 5, 5, 2, 1] 순서로 정렬)

하지만 배열에선 이런 방식으로 정렬할 방법이 없다. (있을지도 모르지만..)

때문에 HashMap을 사용하여 value가 가장 큰 순서로 정렬하는 방향으로 진행하였다.


먼저 Map 자료구조를 만들고 배열의 요소를 key, 요소의 개수를 value로 채운다.

arr.forEach(e => {
    map.has(e) ? map.set(e, map.get(e) + 1) : map.set(e, 1);
})​

 

그리고 map의 value를 내림차순으로 정렬한 배열을 구한다.

const sortedValues = [...map.values()].sort((a,b) => b - a);​

 

마지막으로 sum 변수를 생성하고 values의 첫 요소부터 더한 뒤, 
만약 arr / 2보다 sum이 커지면 멈추는 조건을 추가한다.

for(let value of sortedValues){
    sum += value;
    output++;
    if(sum >= baseSize / 2){
        break;
    }
}​

만약 이때 제거한 요소의 쌍을 찾고 싶으면 map.values가 아니라 map.entries로 key와 value를 모두 구하고
output에 key를 push하면 된다.

 

/**
 * @param {number[]} arr
 * @return {number}
 */
var minSetSize = function(arr) {
    const baseSize = arr.length;
    const map = new Map();
    let output = 0;
    let sum = 0;
    
    arr.forEach(e => {
        map.has(e) ? map.set(e, map.get(e) + 1) : map.set(e, 1);
    })
    
    const sortedValues = [...map.values()].sort((a,b) => b - a);
    
    
    for(let value of sortedValues){
        sum += value;
        output++;
        if(sum >= baseSize / 2){
            break;
        }
    }
    
    return output;
};