(Python/LV2) 시소 짞꿍

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/152996

풀이:

from itertools import combinations, product


def solution(weights):
    count = 0
    lists = tuple(combinations(weights,2))
    times = tuple(product([2,3,4],repeat = 2))
    for list in lists:
        for time in times:
            if list[0] == list[1]:
                count += 1
                break
            if list[0] * time[0] == list[1] * time[1]:
                count += 1
                break
    return count

쉬웠지만 역시 호락호락 하지않다

시간 초과 엄청나게 뜸 29.4/ 100

 

 

 

def solution(weights):
    dic={}
    ratios = [4/2, 4/3, 3/2, 2/3, 3/4, 2/4]
    answer = 0
    for weight in weights:
        if weight in dic:
            dic[weight]+=1
        else:
            dic[weight]=1
    for w in weights:
        for ratio in ratios:
            if int(w*ratio) != w*ratio :
                continue
            if int(w*ratio) in dic :
                answer += dic[int(w*ratio)]

        answer += (dic[w] - 1)
    return answer//2

 

 

일단 시소 기준 왼쪽 오른쪽 배율을 나눈것을 ratios 에 담는다 22/ 33/ 44 는 동일하므로 재끼면 6개가 들어간다.

* 왼쪽에 있는 숫자를 이항에서 계산하는거임 ex 좌2 = 우4 일때 좌 = 우 4/2 이런식

 

dic 을 선언해주고 각 숫자들 나온 갯수를 딕셔너리화 해주면

{100: 2, 180: 1, 360: 1, 270: 1}  이렇게 나온다.

 

for w in weights:
    for ratio in ratios:
        if int(w*ratio) != w*ratio :
            continue
        if int(w*ratio) in dic :
            answer += dic[int(w*ratio)]

    answer +=(dic[w] - 1)

무게 들을 하나 빼주고 (몸무게 * 비율) 들을 해주는데 정수가 아니라 소숫점으로 나오면 제껴야하므로 continue 를 넣어준다.

 

그리고 (몸무게 * 배율) 이 딕셔너리에 들어있으면 균형이 맞는것이다.

 

맨 마지막줄은 무게가 똑같을 때 더해주는것이다. 최소 1개씩 가지고 있으니 -1 을 해줘야한다.

 

return answer//2

 

if int(w*ratio) in dic :
    answer += dic[int(w*ratio)]

에서 양쪽 방향인 경우가 나왔고, 같은수도 뒤집으면 똑같은 경우이기때문에 한번씩 더 된거이므로 answer/2 를 해줘야한다

(x,y) >> (y,x) 

 

ex)

 

for w in weights:
    for ratio in ratios:
        if int(w*ratio) != w*ratio :
            continue
        if int(w*ratio) in dic :
            answer += dic[int(w*ratio)]
    answer += (dic[w] - 1)
return answer//2


print(solution2([100,180,100,360])) 일경우

100 100 / 뒤집은 100 100  2개
180 4/2 //// 360 2/1 이렇게 2개 나온다..

뒤집은 것 까지 계산 했으므로 /2를 해주면 된다.