Level 2 ) 시소 짝꿍 ⭐️

문제 설명

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

---

제한 사항

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

---

입출력 예

weights	result
[100,180,360,100,270]	4

---

입출력 예 설명

{100, 100} 은 서로 같은 거리에 마주보고 앉으면 균형을 이룹니다.
{180, 360} 은 각각 4(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
{180, 270} 은 각각 3(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
{270, 360} 은 각각 4(m), 3(m) 거리에 마주보고 앉으면 균형을 이룹니다.

풀이

처음 생각한 방식

1. 두 수의 최대공약수를 구한다.
2. 각 숫자 / 최대공약수의 값이 4,3,2,1에 포함되면 시소 짝꿍
   => 틀렸다

function solution(weights) {
    let answer = 0;
    let distance = [1,2,3,4];
    
    function fnGCD(a,b){
        return b % a ? fnGCD(b,a%b) : a;
    }
    
    for(let i=0;i<weights.length-1;i++){
        for(let j=i+1;j<weights.length;j++){
            let a = weights[i];
            let b = weights[j];
            let gcd = fnGCD(a,b);
            if(distance.includes(a / gcd) && distance.includes(b / gcd)) answer++;
        }
    }
    return answer;
}

두 번째로 생각한 방식

1. weights의 각 값에 2,3,4를 곱한 배열을 만든다.
2. 값이 같은거(1:1)부터 찾아서 개수를 구한다. (set을 활용)
3. 값이 같은걸 제거 한 후 3개의 배열을 합치고 중복제거를 하여 가능한 시소 짝꿍의 개수를 구한다.
   => 틀림

2 [200, 360, 720, 200, 540]
3 [300, 540, 1080, 300, 810]
4 [400, 720, 1440, 400, 1080]

정답 풀이

1. weights에서 각 숫자의 개수를 dict에 담는다.
   ex. { 100 : 2, 180: 1, 360: 1, 270: 1 }
2. weights를 오름차순으로 정렬한다.
   오름차순으로 정렬하면 1:1, 3:2, 4:2, 4:3 인지만 체크해주면 된다.
3. dict에서 위의 비율에 해당하는 값이 존재하면 answer에 개수를 더해준다.
4. 한 차례가 끝날때마다 해당 값의 개수를 1 빼준다.
   (중복되어 비교되는 것을 막기 위해)

function solution(weights) {
    const dict = {};
    for (let weight of weights) {
       dict[weight] = (dict[weight] || 0) + 1;
    }
    // 오름차순
    weights.sort((a, b) => (a - b));
    let answer = 0;
    for (let weight of weights) {
        // 1 : 1
        if (dict[weight] > 1) answer += (dict[weight] - 1);
        // 3 : 2
        if (dict[weight * (3 / 2)] > 0) answer += dict[weight * (3 / 2)];
        // 4 : 2 -> 2 : 1
        if (dict[weight * 2] > 0) answer += dict[weight * 2];
        // 4 : 3
        if (dict[weight * (4 / 3)] > 0) answer += dict[weight * (4 / 3)];

        // 현재차례가 끝나면 dict[현재차례]에서 -1 해준다.
        // 다음차례에서 현재 weight를 비교대상에서 제외시키기 위해 하나 빼주는 것
        dict[weight] -= 1;
    }
    return answer;
}