[Python] [Level 2] 시소 짝꿍 (Counter 함수 활용하기)

프로그래머스 문제

 

시소 짝꿍

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

프로그래머스

 

 

 

 

 

1차 풀이 (실패)

단순하게 생각해서 

이중 loop로 가능한 조합을 다 대응하는 식으로 풀었더니 안됨...

최대 길이가 100,000이니까 이중 loop는 시간 초과!

"""
시소 2, 3, 4
무게 상쇄 : 짝꿍 
짝궁이 몇 쌍 존재 하는지 구하기
"""
def solution(weights):
    answer = 0
    num = len(weights)
    
    #2, 3, 4
    #1배, 1.5배, 2배 or 1배, 0.75배, 0.5배 
    
    for i in range(num):
        for j in range(i+1, num):
            #print(i, j)
            # 무게가 같다면
            if weights[i] == weights[j] or weights[i]*1.5 == weights[j] or weights[i]*2 == weights[j]:
                answer += 1
            elif weights[i]*0.75 == weights[j] or weights[i]*0.5 == weights[j]: 
                answer += 1
    
    return answer

 

 

 

 

 

2차 풀이 (실패)

Counter 함수로 dict 형태로 만들기

자동적으로 같은 key 의 value 갯수를 새준다 

 

또 다시 수열 계산 때문에 시간 초과

같은 무게일 경우 어떻게 간편하게 계산하지?

"""
시소 2, 3, 4
무게 상쇄 : 짝꿍 
짝궁이 몇 쌍 존재 하는지 구하기
"""

from collections import Counter # 무게의 종류는 901가지

def solution(weights):
    answer = 0
    times = (3/4, 2/3, 1/2)  # 0.75배, 0.333배, 0.5배 
    num = len(weights)
    count = Counter(weights)
    
    # 2 3 4 5  6
    # 1 3 6 10 15 21 
    # 같은 무게일 경우
    for key,value in count.items():
        if value > 1:
            tmp = 1
            for j in range(2, value):
                tmp = tmp + j
    
    answer += tmp

    # 같은 무게가 아닐 경우
    for i in range(num):        
        for j in times:
            if weights[i] * j in weights:
                #print(weights[i])
                answer += 1
            
    
    return answer

 

 

 

 

3차 풀이 (성공)

힌트를 너무 참고 해버렸다

set 함수를 이용해 중복값을 없애므로 계산 시간을 줄였다!

set 함수를 이용안하면 시간 초과 되서 실패한다

"""
시소 2, 3, 4
무게 상쇄 : 짝꿍 
짝궁이 몇 쌍 존재 하는지 구하기
"""
from collections import Counter # 무게의 종류는 901가지

def solution(weights):
    answer = 0
    times = (3/4, 2/3, 1/2)  # 0.75배, 0.333배, 0.5배 
    count_dict = Counter(weights)
    
    # 같은 무게일 경우
    for key, value in count_dict.items():
        # same value  = 2, 3, 4,  5,  6,  7
        # combination = 1, 3, 6, 10, 15, 21 
        if value > 1:
            answer += value * (value - 1) / 2
            
    
    # weights 안에 중복 없애기 
    weights = list(set(weights))
    
    # 같은 무게가 아닐 경우
    for i in weights:    
        for j in times:
            if i * j in weights:
                combination_num = count_dict[i * j] # 조합 갯수
                print(combination_num)
                answer += combination_num * count_dict[i]
            
    return answer