[Programmers / JS] Lv.2 시소 짝꿍

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

프로그래머스

문제 설명

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

---

제한 사항

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

 

Solve

• weightObject를 생성해준 뒤 주어진 weights의 중복된 요소 갯수를 count를 해서 저장해 주었습니다.
• weights 배열을 순회하면서 균형을 이룰 수 있는 조건 (1, 3/2, 2, 4/3)을 확인하며, 해당 무게가 object안에 있다면, 짝꿍을 이룰 수 있는 경우가 있는 것이므로, answer에 값을 더해줍니다. 

Problem

• 주어진 weights의 길이가 최대 100,000까지 주어지기 때문에, 이중 for문을 통한 접근(최대 100억번의 연산)은 어렵겠다고 생각했습니다. 그래서 주어진 weights[i]의 범위를 보니, 최대 901가지의 경우가 나오는 것을 확인하여, 활용해 주었습니다.
• weightsObject의 해당 value값이 1보다 클 경우(중복되는 숫자의 처리)는, 규칙을 찾아 점화식으로 대입해 주었습니다.

Code

function solution(weights) {
    let answer = 0;
    weights.sort((a,b)=>a-b);
    
    const weightObject = {
        
    }
    for(let i = 0; i <weights.length; i++) {
        if(!weightObject[weights[i]]) weightObject[weights[i]] = 0;
        weightObject[weights[i]]++;
    }
    
    const wei = [...new Set(weights)]
    
    for(let i = 0 ; i < wei.length; i++) {
        if(weightObject[(wei[i] * 3/2)]) 
            answer += weightObject[(wei[i] * 3/2)] *weightObject[wei[i]];
        if(weightObject[(wei[i] * 2)]) 
            answer += weightObject[(wei[i] * 2)]*weightObject[wei[i]];
        if(weightObject[(wei[i] * 4/3)]) 
            answer += weightObject[(wei[i] * 4/3)]*weightObject[wei[i]];
        if(weightObject[wei[i]] > 1) answer += ((weightObject[wei[i]] * (weightObject[wei[i]] - 1))/2);
        
    }
    return answer;
    // 이중반복문은 시간초과, weights의 길이가 100,000이기 때문에,
}