[프로그래머스] Level2 - 시소 짝꿍(Javascript)

프로그래머스

 

▶️▶️ 문제 요약

1️⃣ 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.
이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 한다.

2️⃣  즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있다.

3️⃣ 사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성하자.

 

❌ 실패 코드

function balance(a, b) {
    const distance = [2, 3, 4];
    let one = [];
    let two = [];
    // 두 몸무게 같으면 true
    if (a === b) {
        return true;
    } else {
        // one, two 배열에 중심으로부터의 거리를 곱한다. 
        for (let i = 0; i < distance.length; i++) {
            one.push(a * distance[i]);
            two.push(b * distance[i]);
        }
        // Set 함수 사용
        const set1 = new Set(one);
        
        // Some 메서드로 중복 체크 
        const hasDuplicates = two.some(item => set1.has(item));
        
        // 두 몸무게가 다르면 시소 중심으로부터 거리의 지점을 곱했을때 비슷한게 있으면 true
        if (hasDuplicates) {
            return true
        }
    }

}


function solution(weights) {
    let answer = 0;
    
    // 배열 정렬
    weights.sort((a, b) => a - b);
    
    
    // while 문 사용
    while (weights.length > 0) {
        // 배열 앞의 원소를 빼준다.
        let first = weights.shift();
        
        for (const weight of weights) {
            if (balance(first, weight)) {
                answer += 1;
            } 
        }
    }
    return answer

}

❗️실패 이유

👉 정답은 통과하는데 문제가 while문 안에 있는 for문 때문에 시간초과가 난다...

 

 

✅ 정답 코드

function solution(weights) {
    let answer = 0;
    // Map 함수 사용
    const map = new Map();
    // 시소 탈 수 있는 범위가 있는지 체크
    const ratio = [1, 3 / 2, 2, 4 / 3];
    
    // 내림차순 정렬
    weights.sort((a, b) => b - a);
    
    // 무게에 비율을 곱한다.
    for (const w of weights) {
        for (const r of ratio) {
            // 만약 map에 곱한 값이 이미 존재한다면 map에 w * r에 해당하는 값을 가져와서 더한다.
            if (map.has(w * r)) answer += map.get(w * r);
        }
        // w이 없으면 1을 값으로 가지는 키-값을 추가
        // w가 이미 존재하고 있다면 그 값을 n + 1로 업데이트한다. 
        map.set(w, (map.get(w) || 0) + 1);
    }
    return answer
    
}

👉 푸는 방식을 달리해야한다. 입출력 예 설명에서 보면 균형을 이루는 지점이 [같은 몸무게, 4/2(=2), 3/2, 4/3] 이렇게 된다. 

👉 내림차순으로 하면 무거운 무게부터 처리하면, 무거운 무게의 원소들은 이미 맵에 저장되어 있기 때문에 어떤 원소를 곱했을 때 맵에서 같은 값을 빠르게 찾을 수 있다. 

👉 무게에 비율을 곱하고 만약 map에 무게랑 비율을 곱한 값이 존재한다면 answer 해당 값을 가져와서 더한다. 

👉 현재 무게를 map에 저장하는데 똑같은 값이 있는지 체크해서 값을 변경해준다. 

 

 

📝 느낀점

👉 난이도가 높을 수록 시간 복잡도를 고려해야 한다. 그렇기 때문에 적절한 자료구조를 사용해주는 것이 좋다. Map(), Set() 혹은 시간 복잡도가 적게 걸리는 알고리즘을 사용해야 한다.