시소 짝꿍
어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 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 |
⚡️ 풀이
combinations으로 접근했다가 시간초과 나서 레퍼런스 참고함
아이디어 생각해내는게 너무 힘들었다. 🥹
weights의 길이가 최대 10만이기 때문에 O(n^2)보다 좋은 알고리즘을 생각
weights를 한번만 순회하여 답을 구하는 것이 목표
from collections import Counter
def solution(weights):
answer = 0
counter = Counter(weights)
# 1:1(같은거), 2:3, 2:4, 3:4
for i in counter:
print(i)
answer += counter[i] * (counter[i] - 1) // 2
# 같은 수, 조합 공삭이랑 같음 nCr
answer += counter[i] * counter[i * 2/ 3]
answer += counter[i] * counter[i * 2 / 4]
answer += counter[i] * counter[i *3 / 4]
return answer
Hi