Skip to content

Latest commit

 

History

History
76 lines (58 loc) · 4.06 KB

problem.md

File metadata and controls

76 lines (58 loc) · 4.06 KB
Raw

🔍 문제 링크

Level2 시소 짝꿍 문제

📘 문제 설명

어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 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. Map을 이용하여 공통 숫자를 제거하고, 개수를 카운팅한다.
  2. Map을 통해 Set을 만들고, 오름차순으로 정렬한다.
  3. Set에 있는 숫자를 하나씩 가져와서 1:1, 1:2, 2:3, 3:4 비율 중 총족하는 비가 있는지 확인한다.
    • 충족시, count에 가능한 경우의 수를 더해준다.
    • 미충족시, 다음 조합을 확인한다.

✅ 나의 해답코드

function solution(weights) {
  let answer = 0;

  const wMap = new Map();
  weights.forEach((w) => wMap.set(w, (wMap.get(w) || 0) + 1));

  const wSet = [...wMap.keys()];
  wSet.sort();

  const ratios = [1, 4 / 3, 3 / 2, 2];
  wSet.forEach((weight) => {
    for (const ratio of ratios) {
      const target = weight * ratio;
      if (!Number.isInteger(target)) continue;

      const count1 = wMap.get(weight);
      const count2 = wMap.get(target);
      if (weight === target) {
        answer += (count1 * (count1 - 1)) / 2;
      } else {
        if (count2) answer += count1 * count2;
      }
    }
  });

  return answer;
}

🤔고민한점 & 💡배운점

1) 🤔 문제를 읽고 제한사항의 weights를 보며 단순하게 조합이나 이중 for문으로 풀이하면 시간복잡도가 초과할 것이라 예상했다. 제한 사항을 고려한다면 최소한 O(NlogN)의 시간복잡도를 가지도록 고려해야 했다.

weights의 길이가 10만이라도, 요소 weights[i]의 값은 100~1000숫자 안에 들어갔다. 고로 중복을 제거하면 비교할 경우의 수가 현저하게 줄어듬을 알 수 있다.

그래서 먼저 Map을 이용하여 어떤 숫자가 있고, 각 숫자가 몇개씩 존재하는지 정리하면 된다고 생각했다.

2) 🤔 다음으로 고려해야할 점은 시소 짝궁이 되기 위해서 평행을 이루어야 하며, 이는 거리 x 무게의 값이 같아야 충족했다. 이때 거리는 2, 3, 4m만 가능하므로 나올 수 있는 경우의 수는 [2:2, 2:3, 2:4, 3:2, 3:3:, 3:4, 4:2, 4:3, 4:4]이지만, 조합을 고려하고 중복을 제거한다면 [1:1, 1:2, 2:3, 3:4]로 4가지의 비율만 남게 된다.

그래서 1번에서 중복을 제거한 숫자를 기준으로 1배, 4/3배, 3/2배, 2배의 값을 구하고 그 값을 원소로써 가지고 있는지 확인하면 간단하게 개수를 추론할 수 있었다.

※ 풀이 과정은 맞았지만, 중간에 로직을 잘못 작성해서 제법 풀이 시간이 길어졌다. 이런 실수를 하지 않기 위해 다음에 한 번더 풀어봐야겠다.