프로그래머스 - 시소 짝꿍 (Python)

접근방법

1. 그냥 무작정 반복문 돌리기
   시소에서 놓을 수 있는 위치가 2,3,4 이므로 각각 위치할 수 있는 무게가 리스트에 존재하는지 찾아봤다. 당연히 시간은 O(n^2)으로 시간초과
   ex) weight = [100,180,200,270] 이라고 하면, 200이 2m에 위치했을때 가능한 무게는 4m에 100, 3m에 400/3 이니까 그냥 for in 써서 찾았는데 시간 초과

사실 여기서 막혀서 다른 풀이들을 봤는데 이해하는데 한참 걸려서 내 풀이로 다시 정리해봤다. 문제가 친절하지 않아서 좀 헤맨 것 같다. 만약 [100,100,100,200] 이라고 하면 (100,100) 이 한 쌍이 가능한게 아니라 3쌍이 가능하다. 인덱스로 치면 (0,1),(0,2),(1,2) 의 3 쌍이 존재한다. 그리고 4m에 100, 2m에 200 이 가능한데, 이 또한 (0,3),(1,3),(2,3) 의 3 쌍이 존재한다. 총 6 쌍이 존재한다. 결국 Counter를 사용하여 각 무게의 개수를 사용하여 계산한다

2. Counter 사용
   같은 무게인 사람이 n명 이라고 하면 그 무게로 만들 수 있는 경우의 수는 nC2 = n(n-1)/2 이다.
   그리고 서로 다른 무게(100,200)가 n,m 명 이라고 하면 가능한 경우의 수는 n*m 이다.
   또 생각해봐야 할건 시소에서 무게를 올린 순서를 바꾸는 건데
   왼쪽 2m에 200, 오른쪽 4m에 100을 놓는 경우와 반대로 한 두가지 케이스를 모두 (200,100) 한쌍으로 쳐야한다.
   시소에서 올릴 수 있는 무게의 가능한 비율은 2:2, 2:3, 2:4, 3:4 네가지 뿐이다.
   따라서 주석을 포함해 코드를 작성하자면

from collections import Counter
def solution(weight):
    answer = 0
    counter = Counter(weight)
    for k in counter.keys():
    	# 동일한 무게에 대해 nC2 계산. 어차피 n=1 이라면 0이기 때문에 if가 필요없다. 2:2 비율인 무게 계산
        answer+=counter[k]*(counter[k]-1)//2
        # 2:3 비율인 무게에 대해 계산. k*3/2 가 w에 포함된 정수가 아니라면 counter가 0 이 나온다. 
        # k = 180 이라고 하면 무게가 270 인 것의 개수를 찾아서 계산한다.
        # 반대로 k = 270 인 경우 무게가 180 인 것의 개수를 찾으려면 k*2/3을 하면 된다.
        # 즉 2:3 인 비율을 한 번만 찾고 3:2의 비율은 계산하지 않기 때문에 두 번 더하지 않는다.
        answer+=counter[k]*counter[k*3/2]
        # 위와 마찬가지로 더해준다
        answer+=counter[k]*counter[k*2]
        answer+=counter[k]*counter[k*4/3]
        print(k,answer)
    return answer