✅ 문제

어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.

이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.

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

✅ 풀이

제한사항을 확인했을 때, weights의 길이가 최대 100,000이기 때문에 이중 반복문을 사용할 경우 최대 10억 번의 연산이 필요하다. 무조건 시간초과가 발생할 것이라 생각했고, 한번의 반복문으로 풀이하려고 노력했다.

처음 생각해낸 풀이는 그래프를 이용한 풀이방법이다. 각 무게마다 거리에 따른 무게를 계산하여 그래프를 만들어 놓고, 그래프에서 같은 숫자를 찾아나서는 방식인데.. 시간 초과가 발생했고, 결국 다른 분의 코드를 참고하여 풀이했다.

관건은 최대 무게 배열 (거리에 따른 and 거리를 제외한)을 선언해놓고 인덱스를 이용하여 풀이하는 것이다. (100 ≤ weights[i] ≤ 1,000 이기 때문에 최고 무게는 1000 * 4 = 4000) 반복문의 각 반복마다 무게 배열을 참고하여 다음 시소짝궁을 구해나가는 방식.

풀이는 아래와 같다. (주석 참고.)

function solution(weights) {
  let answer = 0;
  // 시소 중심축으로부터의 거리에 따른 무게 배열
  let weightDistance = Array(4001).fill(0);
  // 실제 무게 배열
  let realWeights = Array(1001).fill(0);
  
  for (const w of weights) {
    // 거리에 따른 무게
    const d2 = w * 2;
    const d3 = w * 3;
    const d4 = w * 4;
    
    // 이전에 지나갔던 사람 중 현재 무게와 일치하는 값이 있으면 시소짝궁으로 추가한다.
    answer += weightDistance[d2];
    answer += weightDistance[d3];
    answer += weightDistance[d4];
    
    // 실제 무게가 같은 사람들이 있으면 시소의 거리에 따른 무게가 3배가 됨.
    // 이를 제거하기 위해 실제 무게 배열의 2배만큼 빼줌
    if (realWeights[w] > 0) {
      answer -= realWeights[w] * 2;
    }
    
    realWeights[w] ++;
    weightDistance[d2] ++;
    weightDistance[d3] ++;
    weightDistance[d4] ++;
  }
  
  
  return answer;
}