프로그래머스 - 시소 짝꿍 (JavaScript)

문제 설명

어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.
이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.
사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 2 ≤ weights의 길이 ≤ 100,000
• 100 ≤ weights[i] ≤ 1,000
  • 몸무게 단위는 N(뉴턴)으로 주어집니다.
  • 몸무게는 모두 정수입니다.

 

풀이 1)

function solution(weights) {
    var answer = 0;
    const cal = [3/2, 2, 4/3];
    const weightsList = new Map();
    
    weights.sort((a, b) => a - b).forEach((element) => {
        if (!weightsList.has(element)) {
            weightsList.set(element, 1);
        }
        else {
            weightsList.set(element, weightsList.get(element) + 1);
        }
    });

    for (let weight of weightsList.keys()) {
        let num = weightsList.get(weight);

        if (num > 1) {
            answer += parseInt(num * (num - 1) / 2);
        }

        cal.forEach((c) => {
            let temp = weight * c;

            if (weightsList.has(temp)) {
                answer += num * weightsList.get(temp);
            }
        });
    }
    return answer;
}

V8 엔진은 정렬 알고리즘으로 Tim Sort를 채택하고 있으며, 최악의 경우 시간 복잡도는 O(nlogn)이다.

몸무게를 오름차순 정렬함으로써 평형 조건을 cal과 같이 설정할 수 있다.

 

weights 배열의 길이는 최대 10만이므로, 이중 for문으로 완전 탐색을 수행할 경우 O(n^2)으로 시간 초과가 난다.

 

V8에서 Map은 해시 테이블로 구현되어 있으므로, 탐색 시 시간 복잡도는 O(1)이다.

몸무게와 그 몸무게에 해당하는 사람의 수를 Map으로 관리하면, Map의 특성 상 O(1)의 시간 복잡도로 탐색을 수행할 수 있다. 따라서 Map의 키 갯수만큼만 탐색하면 된다.

 

• 몸무게가 같은 사람이 n명일 때, 짝꿍을 형성하는 가짓수는 nC2
• 몸무게가 a인 사람들과 b인 사람들이 짝꿍을 형성하는 가짓수는 a * b (평형 조건을 만족할 때)

 

풀이 2)

function solution(weights) {
    var answer = 0;
    const cal = [1, 3/2, 2, 4/3];
    const weightsList = new Map();
    
    weights.sort((a, b) => b - a).forEach((element) => {
        cal.forEach((c) => {
            let temp = element * c;
            if (weightsList.has(temp)) {
                answer += weightsList.get(temp);
            }
        });
        if (!weightsList.has(element)) {
            weightsList.set(element, 1);
        }
        else {
            weightsList.set(element, weightsList.get(element) + 1);
        }
    });
    
    return answer;
}

Map의 key에 대한 순회를 하지 않고 바로 weights 배열을 순회하면서 연산을 수행할 수도 있다. 이때 weights 배열은 내림차순으로 정렬하여 cal을 위와 같이 설정한다. weights 배열 자체를 순회하므로 배열 안에 중복되는 몸무게가 많을수록 비효율적이다.

 

한 가지 주의할 점은 Map에 대한 갱신보다 cal에 대한 연산이 우선적으로 수행되어야 한다는 것이다.

 

풀이 3)

function solution(weights) {
    var answer = 0;
    const cal = [3/2, 2, 4/3, 3/4, 1/2, 2/3];
    const weightsList = new Map();
    
    weights.forEach((element) => {
        if (!weightsList.has(element)) {
            weightsList.set(element, 1);
        }
        else {
            weightsList.set(element, weightsList.get(element) + 1);
        }
    });

    for (let weight of weightsList.keys()) {
        let num = weightsList.get(weight);

        if (num > 1) {
            answer += parseInt(num * (num - 1) / 2);
        }

        cal.forEach((c) => {
            let temp = weight * c;

            if (weightsList.has(temp)) {
                answer += num * weightsList.get(temp);
            }
        });
        
        weightsList.set(weight, 0);
    }
    return answer;
}

정렬을 하지 않고 연산을 수행할 수도 있다. 그러나 데이터가 정렬되어 있지 않으므로 cal을 위와 같이 설정해야 한다. 또한 answer에 중복 계산된 값이 들어가지 않도록, 계산을 수행한 key에 대해서는 value를 0으로 바꿔준다. 정렬에 대한 오버헤드가 줄어 총 연산에 걸리는 시간이 가장 적었다.