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

문제 정보

제목 : 시소 짝꿍

난이도 : Lv.2

사용 언어 : Python

문제 링크

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

프로그래머스

 

문제 설명

어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.
이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.
사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

• 2 ≤ weights의 길이 ≤ 100,000
• 100 ≤ weights[i] ≤ 1,000
  • 몸무게 단위는 N(뉴턴)으로 주어집니다.
  • 몸무게는 모두 정수입니다.

입출력 예

weights	result
[100,180,360,100,270]	4

 

입출력 예 설명

{100, 100} 은 서로 같은 거리에 마주보고 앉으면 균형을 이룹니다.
{180, 360} 은 각각 4(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
{180, 270} 은 각각 3(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
{270, 360} 은 각각 4(m), 3(m) 거리에 마주보고 앉으면 균형을 이룹니다.

---

나의 풀이

문제의 이해

탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이므로 몸무게 비율이 1:1, 2:3, 2:4, 3:4를 만족하면 되고 구해야하는 것은 시소 짝꿍의 쌍 개수입니다.

 

문제의 접근법

weights의 길이가 길기 때문에 모두 순회하여 계산하면 시간초과가 발생하므로, Counter을 이용해 몸무게별 사람의 수를 구한 후, 같은 몸무게인 사람들은 먼저 계산하고 중복을 제거 후 다른 몸무게를 가진 사람 중 비율을 만족하는 수를 answer에 추가했습니다.

 

코드

def solution(weights):
    answer = 0
    seesawRate = [2/3,2/4,3/4]
    wCounter = Counter(weights)
    
    # 같은 몸무게인 사람들끼리 짝꿍의 수 계산함
    for k, v in wCounter.items():
        if v >= 2 :
            answer += v*(v-1)//2
    weights = set(weights)
    
    # 다른 몸무게인 사람들끼리 조합하여 계산함
    for w in weights :
        for s in seesawRate :
            if w*s in weights : # 몸무게 비율이 맞는 사람을 찾음
                answer += wCounter[w*s]*wCounter[w]
    
    return answer