Equalize the Array

Algorithms

Equalize the Array

seoca 2020. 12. 11. 00:10

주어진 array 에서 최대로 중복되는 index를 제외한 나머지 index의 수를 구하는 문제

solution

1. 중복을 허용하지 않는 hashMap 을 선언.

2. 주어진 arr를 hashMap안에 넣으면서 중복되는 값이 있으면 value의 값이 1씩 증가하게 한다.

3. maximum value의 수를 찾는다.

4. 전체 array길이에서 찾아낸 maximum value를 return한다.

Solution 1

-object를 이용하는 traditional way 말고 built-in function 인 Map을 이용하는 방식.

function equalizeArray(arr) {
    //let arrObj = {}; //initialize object which is for hashmap.
    //but using js object is traditional way to make hashmap
    const arrObj = new Map();

    let maxCount = 0;

    //find duplicate index and remove them using hashmap because hashMap doesnt allow duplicates
    for (let num of arr) {
        arrObj[num] = arrObj[num] + 1 || 1;
    }
    
    for (let value in arrObj) {
        if (arrObj[value] > maxCount) {
            maxCount = arrObj[value];
        }
    }
        
    return (arr.length - maxCount);
}

- Javascript {} 는 Object initialization.

- Javascript object는 hashmap 을 만드는 traditional way.

- for (let num of arr) {
arrObj[num] = arrObj[num] + 1 || 1; // 처음에 num 이 arrObj[num] 에 있으면 true 아니면 falsy. 처음에는 없으니 1이 들어간다.
}

- arrObj[num] 이런식으로 넣으면 key값으로 들어간다.

Solution 2

const arr = [3, 3, 1, 4, 3, 4];

function equalizeArray(arr) {
    let object = new Map();

    //count the duplication
    for (let num of arr){
        if(!object[num]) object[num] = 0;
        object[num]++;
    }

    //Return the number with the highest value
    //Object.value() returns an array
    let mostRepeated = Math.max(...Object.values(object)); 
    
    let result = arr.length - mostRepeated;

    //return result;
    return result;
}

let result = equalizeArray(arr);
console.log(result);