[프로그래머스: 시소 짝꿍] (Python)

문제 - 문제링크 

문제 풀이 아이디어 

•  weights 순회하면서 dic에 해당 무게를 가진 사람 수 카운팅 
• 각 무게를 탐색하면서 
  • (1) 무게가 같은 사람들 -> nC2 , 두명을 뽑아 짝꿍 만들기 
  • (2) 무게가 같지 않은 경우 [1:2, 2:3, 3:4] 비율을 만족하는 무게를 가진 사람들과 짝꿍 가능
    -> 해당 무게의 사람 수*(비율을 만족하는 무게의 사람들의 수

알아둘 개념 

• dic.get(찾는 원소, 없으면 대신 리턴할 값) -> x in dic  하지 않고 이렇게 없으면 바로 리턴할 값을 지정하는 매소드 활용하기 

리뷰 

• 처음에 모든 사람들의 무게를 서로 한 번씩 비교함-> 시간초과 O(N^2)
• 무게가 같은 사람이 여러명 있으면 굳이 또 비교하는 과정이 없어도 됨-> dic 활용 로직으로 시간복잡도 개선함 

코드 구현 

def solution(weights):
    answer = 0
    
    dic = {}
    for w in weights:
        dic[w] = dic.get(w, 0)+1
    # print(dic)
    
    for w in dic.keys():
        if dic[w] >1: #같은 무게인 사람들 
            answer += (dic[w]*(dic[w]-1))/2
        answer += dic[w]*(dic.get(w*2, 0)+dic.get(w*(2/3), 0)+dic.get(w*(3/4), 0))

	return answer