[프로그래머스] 시소 짝꿍(Lv 2)

https://school.programmers.co.kr/learn/courses/30/lessons/152996

프로그래머스

우선 무게 배열 크기가 10만까지이다. O(n^2)일 경우, 100억으로 TLE 확정이다.
(TIP : 1억까지가 확정)

즉, 반복문을 돌려서 풀 수 없는 문제이다.

잘 생각해보면, 무게당 몇명인지만 알면 인원수의 계산이 가능하다.
같은 무게일 경우에는 2명씩만 짝지으면 되고 다른 무게끼리는 인원수끼리 곱하는 경우의 수 문제.

def solution(weights):
    answer = 0
    weight_dict = {}
    for w in weights:
        if w not in weight_dict:
            weight_dict[w] = 1
        else:
            weight_dict[w] += 1
    for w in weight_dict:
        if weight_dict[w] > 1:
            answer += weight_dict[w] * (weight_dict[w]-1) / 2
        if w * 2 in weight_dict:
            answer += weight_dict[w] * weight_dict[2 * w]
        if w * 3 / 2 in weight_dict:
            answer += weight_dict[w] * weight_dict[3 / 2 * w]
        if w * 4 / 3 in weight_dict:
            answer += weight_dict[w] * weight_dict[4 / 3 * w]
    return answer