[JS] 시소 짝꿍

내가 가진 무게로, 시소를 탈 수 있는 범위가 있는지 없는지 알아내야 하는게 문제인데, includes와 같은 탐색 함수는 시간복잡도가 O(n) 이므로 시간을 많이 잡아먹게 된다. Map 자료형을 활용해서 이를 O(1)만에 찾을 수 있도록 구현하여 해결하였다.

 

 

나와 같은 몸무게인 경우에는, Map자료형의 내 몸무게 개수에서 1을 뺀 값을 더해주고, 아닌 경우에는 Map자료형만큼 가져와주었다.

 

 

 

 

 

function solution(weights) {
    let ret = 0
    const map = new Map()
    for (const weight of weights){
        if (map.get(weight)) map.set(weight,map.get(weight)+1)
        else map.set(weight,1)
    }
    const ary = [2/3,2/4,3/2,3/4,4/2,4/3,1]
    
    for (let i = 0 ; i<weights.length ; i++) {
        const a = weights[i]
        for (const b of ary){
            const num = map.get(a*b)
            
            if (num){
                 if (a*b===a && num>1) ret += num-1
                 else if (a*b!==a)ret += num
            }
        }
     
    }
    
    return ret/2
}