프로그래머스 - Level 2. 시소 짝꿍 / JavaScript (js)

문제설명

문제분석

시소가 평형을 이루기 위해서는 양쪽의 토크가 같아야 합니다. 먼저 토크를 구하는 공식을 살펴보겠습니다.

t = F(N) * r(m) * sinΘ

토크(t)는 회전축으로부터의 거리(r)와 아래로 누르는 힘(F)과 누르는 각도(sinΘ)의 곱입니다. 이 문제에서는 시소에 사람이 탑승하므로 각도를 제외하고, 아래로 누르는 힘을 대신해 몸무게를 사용합니다. 회전축으로부터의 거리는 2m, 3m, 4m 중 하나이고, 반대쪽에도 같은 거리에 사람이 탑승합니다. 따라서 다음과 같은 공식을 구할 수 있습니다.

t_1 = N_1 * r_1 = N_2 * r_2 = t_2

먼저 탑승한 사람을 정하고, 먼저 탑승한 사람의 토크를 계산합니다. 그리고 나머지 사람을 순회하며  토크를 구하고 먼저 탑승한 사람의 토크와 비교하여 같은 경우 answer 카운트를 올려줍니다.

 

문제를 단순화 했으니 이해하기 쉽게 코드를 짜보겠습니다.

이해하기 쉽게 코드작성하기

function solution(weights) {
    let answer = 0;
    for(let i = 0; i < weights.length - 1; i++) {
        const prev = [2, 3, 4].map(x => x * weights[i]);
        for(let j = i + 1; j < weights.length; j++) {
            const pair = [2, 3, 4].map(x => x * weights[j]);
            if(prev.filter(x => pair.includes(x)).length > 0) answer++;
        }
    }
    return answer;
}

그러나 역시나 다음과 같이 시간초과라 결과를 만나게 됩니다.

이 문제를 조금 더 가볍게 만들어보겠습니다. 먼저 탑승한 사람을 기준으로, 짝꿍에 대한 일반항을 만들면 다음과 같습니다.

N_1 = N_2 * r_2 / r_1

현재 사용자의 무게를 먼저 선택했을 때, 짝꿍의 무게 곱하기 r_2 / r_1의 결과값 중 하나여야 합니다. 따라서 거리에 대해 가능한 비율이 [2/2, 3/2, 4/2, 4/3]이므로, 그 비율을  [1, 3/2, 2, 4/3]으로 결정할 수 있습니다. 각 비율이 저렇게 나오는 이유는 r_1 : r_2가 중복되지 않는 경우를 나타낸 것으로 (2, 2), (2, 3), (2, 4), (3,4)가 존재하기 때문입니다. (3, 3)과 (4, 4)는 비율상 (2, 2)와 동일합니다.

 

문제 해결을 위해 접근하면, 몸무게를 먼저 내림차순으로 정렬합니다. 가장 무거운 사람을 기준으로 전체 요소를 순회하며 이 사람의 무게를 가진 사람의 수를 기록합니다. 점점 다음 사람으로 넘어가면서 몸무게 * 거리비에 해당하는 값이 기록된 몸무게 중에 존재한다면 answer에 해당 기록을 추가합니다. 이 설명을 코드로 작성하면 다음과 같습니다.

 

function solution(weights) {
    const distanceRate = [1, 3/2, 2, 4/3];
    const memo = {};
    let answer = 0;
    
    weights.sort((a, b) => b - a);
    
    for(const el of weights) {
        distanceRate.forEach(x => {
            const t = el * x;
            if(memo[t] !== undefined) answer += memo[t];
        });
        memo[el] = (memo[el] || 0) + 1;
    }
    return answer;
}