✅ 문제

---

문제 바로가기

✅ 나의 풀이

---

첫번째 시도 (시간 초과)

# 실패 (시간 초과)
def solution(weights):
    cnt = 0
    weights.sort()

    for i in range(len(weights) - 1):
        for j in range(i+1, len(weights)):
            a = weights[i]
            b = weights[j]

            if a == b: cnt += 1 
            elif b == 2*a: cnt += 1
            elif b == 3*a / 2: cnt += 1
            elif b == 4*a / 3: cnt += 1

    return cnt

알고리즘

1. weights를 오름차순으로 정렬
2. weights의 모든 조합 (a, b)에 대하여 요소 a, b가 1:1, 1:2, 2:3, 3:4의 비율을 갖는지 확인, 맞으면 cnt 증가시킴
   ex) weights = [100, 100, 180, 270, 360]
   (100, 100) → 1:1
   (100, 180) → X
   (100, 270) → X
   (100, 360) → X
   (100, 180) → X
   ...
   (270, 360) → 3:4

결과 : 시간초과

하지만, 이 경우 중첩for문이 사용되어 최악의 경우 100,000 * 100,000번의 연산을 해야 하므로 시간초과다.

두번째 시도 (통과)

from collections import Counter

def solution(weights):
    cnt = 0
    weights.sort()
    counter = Counter(weights)

    for i in range(len(weights) - 1):
        w = weights[i]
        
        cnt += counter[w] - 1
        cnt += counter[2*w]
        cnt += counter[3*w / 2]
        cnt += counter[4*w / 3]
        
        counter[w] -= 1
        
    return cnt

알고리즘

1. weights를 정렬한다.
2. Counter()를 사용하여 weights의 counter를 만든다.
   ex) {100:2, 180:1, 270:1, 360:1
3. weights를 순회하며 1:1, 1:2, 2:3, 3:4의 비율을 갖는 수가 counter에 있는 경우 그 수만큼 cnt를 증가시킨다.
4. 중복계산을 방지하기 위해 counter에서 현재 요소의 개수를 1 감소 시킨다.