Lv2. 시소 짝궁

[Lv2. 시소 짝궁]

문제 설명

어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 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

---

내 풀이

def solution(weights):
    answer = 0
    ratios = [1, 2/3, 0.5, 1.5, 0.75, 4/3]
    for i in range(len(weights)):
        for j in range(i+1, len(weights)):
            if weights[i]/weights[j] in ratios:
                # print(weights[i], weights[j], weights[i]/weights[j])
                answer += 1
    return answer

처음에 짰던 풀이.. 눈물 좔좔 남
더블 룹 때문에 time complexity O(n^2)이라 시간 초과가 너무 많이떴었다
해싱이나 딕셔너리 쪽을 쓰는게 좋겠다고 생각은 했는데 어떻게 하지 고민하다가 defaultdict 발견

from collections import defaultdict
def solution(weights):
    answer = 0
    dict = defaultdict(int)
    #defaultdict은 말 그대로 딕셔너리 생성자 (그런데 타입을 지정해줄 수 있는 - int, set...)
    for weight in weights:
        answer += dict[weight]+ dict[weight/2] + dict[weight*2] + dict[weight*2/3] + dict[weight*3/2] + dict[weight*3/4] +dict[weight*4/3]
        dict[weight] += 1
    return answer

이렇게 수정했다
외부 라이브러리를 썼긴 하지만 어찌저찌 해결은 .. 했다는 것
비율가짓수(시소 거리)가 몇개 되지 않는데도 불구하고 생각보다 케이스가 많아서 당황했다 더 많아졌을때 general solution을 찾을 수 있는 방법에 대해서도 생각해봐야함

다른 사람 풀이

from itertools import combinations
from collections import Counter

def solution(weights):
    cnt = 0
    weights = Counter(weights)
    for a, b in combinations(weights.keys(), 2): # 서로 다른 무게
        if a*2 == b*3 or a*2 == b*4 or a*3 == b*4 or b*2 == a*3 or b*2 == a*4 or b*3 == a*4:
            cnt += weights[a] * weights[b]
    for v in weights.values(): # 같은 무게
        if v > 1:
            cnt += sum([i for i in range(1, v)])
    return cnt

다른 사람 풀이 구경하다가 당황했던 건데 combinations써도 .. 괜찮았던거임..? 어째서..? time complexity .. 왜..?