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

💡 문제 설명 

어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.
이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의

크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다.

즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.
사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution

함수를 완성해주세요.

 

 

제한 사항

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

 

입출력 예

 

 

입출력 예 설명

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

 

---

 

🙋🏻‍♀️ How I Solve (시간 초과 실패)

시간 복잡도 생각을 못하고 이중 반복문으로 풀었더니 시간 초과가 떴다.

10^5 * 10^5 = 10^10승 이므로 당연히 실패라 뜬다..

 

def solution(weights):
    answer = 0
    same = 0 
    
    for i in range(len(weights)):
        for j in range(len(weights)):
            if i == j:
                continue  
            if weights[i] * 2 == weights[j] * 2:
                same += 1
            elif weights[i] * 2 == weights[j] * 3:
                answer+= 1
            elif weights[i] * 3 == weights[j] * 4:
                answer += 1
            elif weights[i] * 2 == weights[j] * 4:
                answer+= 1 
                
    result = (same/2) + answer
    return result

 

🙋🏻‍♀️ How to Solve (성공)

반복문을 한번만 사용해서 풀어야 시간 초과가 안난다. 

 

이 문제는 collections 모듈의  Counter를 사용해야한다. 

Counter는 컨테이너안의 데이터를 편리하고 빠르게 개수를 세도록 지원하는 계수기 도구이다. 

 

1) 1:1인 경우

weights 배열 안에 같은 숫자가 몇개 있는지를 확인하기 위해 counter 모듈을 사용한다. 

테스트케이스를 확인해보면 

Counter({100: 2, 180: 1, 360: 1, 270: 1})

이렇게 키와 값으로 dict 형식으로 출력이 되는 것을 알 수 있다. 

100kg인 사람이 두 명있다. 

 

반복문으로 counter의 값이 2이상일 경우, (사람 수 * (사람 수 -1)) / 2를 하여 1:1인 경우를 알 수 있다. 

 

 

2) 2:3, 2:4, 3:4 인 경우

1:1인 경우는 이미 구했으니 weigths 배열 안에서 중복되는 값은 빼준다. -set() 활용하여 중복 제거 

(참고: counter 안에 이미 사람 수가 저장 되어 있으므로 나중에 계산하는데 문제 없음)

 

중복을 제거한 weights를 반복문으로 돌면서 2:3일 때, 2:4일 때, 3:4일 때

counter에 들어있는 사람의 수들을 곱하여 answer에 더해준다.  

 

 

🖥️ code

from collections import Counter


def solution(weights):
    answer = 0
    
    # 1:1
    counter = Counter(weights)
    for key,value in counter.items():
        if value>=2:
            answer+= value *(value-1)//2
            
    weights = set(weights) #1:1 구한 후 중복 제거  
    
    #2:3, 2:4, 3:4
    for w in weights:
        if w*2/3 in weights:
            answer+= counter[w*2/3] * counter[w]
        if w*2/4 in weights:
            answer+= counter[w*2/4] * counter[w]
        if w*3/4 in weights:
            answer+= counter[w*3/4] * counter[w]
    return answer

 

 

 

 

---

 

시소 짝꿍 문제 풀러가기

프로그래머스