프로그래머스 level2 [시소 짝꿍] 파이썬

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

프로그래머스

#프로그래머스 level2 시소 짝꿍
from collections import defaultdict
def solution(weights):
    answer = 0
    length=len(weights)
    dic=defaultdict(int)
    for weight in weights:
        dic[weight]+=1
    
    for weight in dic.keys():
        if dic[weight]>1:
            answer+= dic[weight]*(dic[weight]-1)//2
        if weight *2 in dic.keys():
            answer+= dic[weight] *dic[weight*2]
        if weight *3/2 in dic.keys():
            answer += dic[weight] * dic[weight*3/2]
        if weight *4/3 in dic.keys():
            answer+=dic[weight]*dic[weight*4/3]
    return answer

print(solution([100,180,360,100,270]))

맨 처음에는 O(N^2)으로 해결하려고 하였다. 하지만, 시간 초과로 문제가 해결되지 않았다.

(최대 길이가 10만이므로, 10만*10만 == 100억...)

dictionary를 이용하여 해결하려 하였는데, 같은 수가 있는 경우를 어떻게 처리해야할지 난감했다. 한참을 고민해도 떠오르지 않아 다른 분의 풀이를 참고하여 해결하였다.

 

https://velog.io/@pindum/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%8B%9C%EC%86%8C-%EC%A7%9D%EA%BF%8D-Python <-- 참조 블로그