시소 짝궁

시소 짝궁 (프로그래머스)

https://school.programmers.co.kr/learn/courses/30/lessons/152996#qna

문제 설명

어느 공원 놀이터에는 시소가 하나 설치되어 있습니다.

이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.

이 시소를 두 명이 마주 보고 탄다고 할 때,

시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어

완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다.

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

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

풀이

비율을 이용하면 된다

2(m), 3(m), 4(m) 거리의 지점에 좌석이 있고 좌석간의 비율을 이용하여 풀면 된다

2와3은 2:3 비율이다, 2와4는 1:2 비율이다, 3과4는 3:4비율이다,

성능개선

문제를 풀다가 시간초과가 걸렸다

반복을 많이 돌아서 그런거같다

성능개선을 위해 new Array(1001).fill(0) 로 배열을 만들었고 각 인덱스는 weights의 갯수를 의미한다

ex) 100이 2개 있을경우 arr[100]은 2가 된다

이렇게 한 이유는 중복값을 한번에 계산하기 위함이다

ex) 100,100,200 =>

현재값 100 비교값 200일때 (1:2 비율) =>

arr[100] x arr[200] = 2 x 1 = 2

또한 100~1000까지(weights 범위) 반복문을 돌면서 if(arr[i] !== 0)문으로 weights값이 존재하지 않을경우 동작하지 않게 만들었다

function solution(weights) {
    let result = 0;

    // weights길이만큼 생성
    const arr = new Array(1001).fill(0);

    for (const w of weights) {
        arr[w] += 1;
    }

    // weights는 100 ~ 1000이하의 숫자이기 때문에 100~1000까지 반복
    for (var i = 100; i < arr.length; i++) {
        // arr[i] => weights값
        if (arr[i] !== 0) {
            // 동일한 weights값이 존재할때(중복 짝궁을 허용) => 100,100,100 => (총갯수 x 중복횟수) = 6
            result += (arr[i] * (arr[i] - 1)) / 2;

            // 조건 weights는 1000초과하지 못한다

            // 현재값 : 비교값, 1 : 2 비율인 경우 1:2, 2:4
            if (i * 2 <= 1000) {
                result += arr[i] * arr[i * 2];
            }

            // 현재값 : 비교값, 2 : 3 비율인 경우
            if ((i * 3) % 2 === 0 && (i * 3) / 2 <= 1000) {
                result += arr[i] * arr[(i * 3) / 2];
            }

            // 현재값 : 비교값, 3 : 4 비율인 경우
            if ((i * 4) % 3 === 0 && (i * 4) / 3 <= 1000) {
                result += arr[i] * arr[(i * 4) / 3];
            }
        }
    }
    return result;
}