[프로그래머스 Lv2.] 시소 짝꿍(python)

1. 문제

문제 설명

제한사항

입출력 예시

입출력 예 설명

---

2. 풀이 과정

내가 생각한 진행 과정

• 단순히 이중 for문으로 접근했다가 실패함...ㅠ
  • 최대 O(N^2) = 100억 => 시간초과
• 무게가 같은 두 원소 : nC2로 구하기
• 무게가 다른 경우 : 2, 3, *4 비교
  • 이때, 무게가 같은경우 제외하고 진행해야하니깐 set으로 중복 제거한다.
  • 이후에 2, 3, *4 했을 때 균형을 이루는 경우에 중복될 수 있기 때문에 각각의 무게의 (중복되는) 갯수를 곱해야 함.
  • weights = [100, 100, 100, 150, 150, 200, 300]의 경우에는 100과 150을 비교할 때 균형을 이룬다. 그러므로 100의 3개, 150의 2개를 곱한 값을 더해줘야함(Count함수로 구한 것에 갯수 있음)

최종 코드

from collections import Counter

def solution(weights):
    
    temp = Counter(weights)
    
    answer = 0
    for key, val in temp.items():
        if val >= 2:
            answer += val * (val-1) / 2
    print(answer)
    
    weights = set(weights)
    for weight in weights:
        if weight * 2/3 in weights:
            answer += temp[weight] * temp[weight*2/3]
            # print(temp[weight])
            # print(answer)
        if weight * 2/4 in weights:
            answer += temp[weight] * temp[weight*2/4]
            # print(temp[weight])
            # print(answer)
        if weight * 3/4 in weights:
            answer += temp[weight] * temp[weight*3/4]
            # print(temp[weight])
            # print(answer)
    
    return answer