[프로그래머스] 시소 짝꿍

문제_

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

레벨2

풀이_

1. 두 명이 각각 시소에 앉아, 평형을 이루는지를 확인
   • 무게가 각각 x y이고 위치가 각각 a b라고 할 때,
     평형상태일 수 있는 조건: x * a = y * b
   • 즉 y의 무게는 x * a / b
2. x의 무게를 알고 있을 때 y의 무게를 구하려면 a와 b에 값을 일일이 넣어보아야 한다.
   • x와 y를 각각 집어 계산을 진행해야하므로, O(n^2)
3. 2에서 구한 y의 무게는 정수여야 하며, weights의 안에 있어야 한다.
   • weights를 탐색하는 시간을 줄이면 O(n) 시간에 계산이 가능
   • 상수 시간에 검색할 수 있도록 weights의 값을 보관하는 map 생성
4. { 몸무게: 해당 몸무게인 사람의 인원 수 }인 map을 생성
5. map을 순회하면서 다음과 같은 조건을 확인
   a. 해당 몸무게인 사람이 2명 이상인 경우, 서로 평형을 이룰 수 있다. n명으로 만들 수 있는 조합의 수는 nC2이다.
   b. 해당 몸무게를 2, 3, 4미터 지점에 두고, 상대 역시 2, 3, 4지점에 둔다고 가정했을 때 나올 수 있는 몸무게를 구한다.
   c. 해당 몸무게의 사람이 있는 경우, 서로 평형을 이룰 수 있다. 이 경우, x와 y명으로 만들 수 있는 경우의 수는 x * y이다.
6. 조건에 해당하는 경우의 수를 세어 반환한다.

def solution(weights):
    count = 0
    positions = [(2, 3), (2, 4), (3, 4), (4, 3), (4, 2), (3, 2)]

    # 초기화
    weight_map = {}
    for weight in weights:
        weight_map.setdefault(weight, 0)
        weight_map[weight] += 1

    for my_weight in weight_map:
        # 본인이랑 같은 무게의 친구가 있을 경우
        if weight_map[my_weight] > 1:
            count += weight_map[my_weight] * (weight_map[my_weight] - 1) // 2
        # 본인의 몸무게로 평형을 맞출 수 있는 경우
        for (my_position, friend_position) in positions:
            expected_friend_weight = my_weight * my_position / friend_position
            if (expected_friend_weight in weight_map):
                count += weight_map[my_weight] * weight_map[expected_friend_weight]
        # 이미 계산을 끝낸 몸무게는 중복 계산이 되지 않도록 제거해준다
        weight_map[my_weight] = 0

    return count

여담

• 최대공약수를 이용해도 풀 수 있을 것 같아요.
• 처음에 친구 몸무게를 정수로 맞춘다고 int()함수를 씌웠는데, 이렇게 하면 사실 정수가 아닌 몸무게도 정수가 되어버리는 문제가 있어서(예를 들어 25.3인 경우 25가 되어 버림) float형 그대로 써야 했어요.