문제

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

제한 사항

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

풀이

아이디어

• 일단 최대 weights 배열의 길이가 100,000이므로 O(N^2)으로 짜면 절대 안 된다.
• 따라서, 내장 객체 Map을 사용한다.
• 일단 weights 배열을 오름차순 정렬한다. 그리고, 문제 조건에 맞는 비율들을 정리한다.
  • ratios = [1, 1/2, 2/3, 3/4]
    (ratios를 [1, 2, 3/2, 4/3]으로 하지 않는 이유는 다음 로직을 수행할 때 weights가 오름차순 정렬되어 있기 때문에 방문했던 무게를 찾기 위해서이다.)
• 그리고 weights 배열을 순회하면서 다음 로직을 수행한다.
  • ratios 배열을 순회하면서 weight * ratio 값이 Map에 key로 있는지 검사한다.
    • 존재한다면 answer에 키에 해당하는 값만큼 증가시켜준다.
  • Map에 해당 무게를 키로 추가하고, 값은 1 추가한다.

이렇게 해서 최종 answer를 리턴하면 된다.

코드

function solution(weights) {
    let answer = 0;
    weights.sort((a, b) => a - b);
    
    const visited = new Map();
    const ratio = [1, 1/2, 2/3, 3/4];
    
    weights.forEach(weight => {
        ratio.forEach(ratio => {
            const num = weight * ratio;
            if(Number.isInteger(num) && visited.has(num)) answer += visited.get(num);
        })
        visited.set(weight, (visited.get(weight) | 0) + 1);
    })
    
    
    return answer;
}