[프로그래머스] Lv2. 시소 짝꿍 - JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 2

출처 : 프로그래머스 - 시소 짝꿍

문제

제한사항

📌 내가 생각한 풀이

사람의 수가 2명~100000명이다. 2중 for문을 사용하면 최대 100억번이 나오므로 시간초과가 무조건 발생한다. fora문을 한번만 돌기위하여 Hash 맵을 사용하여 해당값의 비율(1, 1/2, 2/3, 3/4)을 곱한것이 존재하는지 확인하고 값을 더해주자.

function solution(weights) {
  var answer = 0;
  let cash = {};
  let caseArr = [1, 1 / 2, 2 / 3, 3 / 4];
  weights.sort((a, b) => a - b);
  weights.forEach(data => {
    caseArr.forEach(d => {
      let val = d * data;
      if (cash[val] !== undefined) {
        answer += cash[val];
      }
    });
    cash[data] === undefined ? (cash[data] = 1) : cash[data]++;
  });

  return answer;
}

📌 느낀점

Hash맵을 사용하면 O(1) 시간에 값을 찾을 수 있다. 이를 이용해 시간 복잡도를 줄이고 이분탐색을 이용하여 하는 방법도 존재할 것 같은데 한번 계속 연구해봐야겠다.