시소 짝꿍

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

생각의 흐름을 따라... 

from itertools import product, combinations


def solution(weights):
    answer = 0
    for w1, w2 in combinations(weights, 2):
        for seat1, seat2 in product((2, 3, 4), repeat=2):
            if w1 * seat1 == w2 * seat2:
                answer += 1
                break
    return answer

시간초과~! 레벨 2도 어렵다. 

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.02ms, 10.2MB)
테스트 3 〉	통과 (0.04ms, 10.1MB)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	실패 (시간 초과)
테스트 13 〉	실패 (시간 초과)
테스트 14 〉	실패 (시간 초과)
테스트 15 〉	실패 (시간 초과)
테스트 16 〉	통과 (0.01ms, 10.3MB)
테스트 17 〉	통과 (0.02ms, 10.1MB)

문제를 보니 리스트가 10만 개 -0-

그러면 저 반복문을 줄여야 하는데... 

모든 조합을 카운트 후 정리해 볼까?

from itertools import combinations

def solution(weights):
    counter = {}
    for i, weight in enumerate(weights):
        for j in (2, 3, 4):
            counter.setdefault(weight * j, set())
            counter[weight * j].add(i)
    answer = set()
    for value in counter.values():
        if len(value) > 1:
            for each in combinations(value, 2):
                answer.add(tuple(sorted(each)))
    return len(answer)

조금 나아지긴 했지만 시간 초과

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.06ms, 10.1MB)
테스트 3 〉	통과 (0.03ms, 10.2MB)
테스트 4 〉	통과 (168.59ms, 34.8MB)
테스트 5 〉	통과 (597.69ms, 102MB)
테스트 6 〉	통과 (1844.77ms, 198MB)
테스트 7 〉	통과 (2662.03ms, 369MB)
테스트 8 〉	통과 (5511.79ms, 719MB)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	실패 (시간 초과)
테스트 13 〉	실패 (시간 초과)
테스트 14 〉	실패 (시간 초과)
테스트 15 〉	실패 (시간 초과)
테스트 16 〉	통과 (0.01ms, 10.1MB)
테스트 17 〉	통과 (0.01ms, 10.4MB)

테스트를 해보니
두 번째 for문에서 시간이 심하게 걸림. 
컴비네이션을 쓰지 말아야... 
그러면 모든 조합을 찾는 과정도 쓰지 말아야... 

def solution(weights):
    answer = 0
    counter = {}
    for i, weight in enumerate(weights):
        counter.setdefault(weight, set())
        counter[weight].add(i)
    for weight in tuple(counter.keys()):  # set(weights)
        length = len(counter[weight])
        for a, b, c in ((2, 3, 4), (3, 4, 2), (4, 2, 3)):
            if (temp := weight * a / b) in counter:  # float과 int를 넘나드는 건 좋지 않다.
                answer += len(counter[temp]) * length
            if (temp := weight * a / c) in counter:
                answer += len(counter[temp]) * length
        if length > 1:
            answer += length * (length - 1) // 2
        del counter[weight]
    return answer

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.02ms, 10.2MB)
테스트 4 〉	통과 (4.84ms, 11.1MB)
테스트 5 〉	통과 (8.11ms, 13.1MB)
테스트 6 〉	통과 (23.09ms, 13.8MB)
테스트 7 〉	통과 (13.60ms, 14.3MB)
테스트 8 〉	통과 (18.37ms, 15.6MB)
테스트 9 〉	통과 (29.08ms, 22MB)
테스트 10 〉	통과 (38.47ms, 24.1MB)
테스트 11 〉	통과 (35.99ms, 23.9MB)
테스트 12 〉	통과 (27.05ms, 22.2MB)
테스트 13 〉	통과 (28.95ms, 21.1MB)
테스트 14 〉	통과 (35.02ms, 21.3MB)
테스트 15 〉	통과 (28.23ms, 21.1MB)
테스트 16 〉	통과 (0.01ms, 10.1MB)
테스트 17 〉	통과 (0.01ms, 10.2MB)