시소짝꿍(프로그래머스) 문제풀이

문제 

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

프로그래머스

 

 

 

문제 접근 방식

시소의 균형이 맞춰지는 페어를 구하는 구현 문제이다. 단순히 생각했을 때, 모든 사람을 이중 for문으로 순회하며 비교할 수 있으나 weights의 최대 길이가 1e5이므로 시간 초과될 확률이 높아서 각 사람들의 무게를 딕셔너리 자료형을 활용해 저장하고 이를 활용해야한다. 간단한 문제인 것 같으나 고려해줘야할 부분이 몇가지 있다. 

 

 

딕셔너리에 어떻게 저장할 것인가?

문제를 처음 접근했을 때, 딕셔너리 자료구조에 기존 무게에 x2, x3, x4한 값을 key로 넣고 value에는 해당 key의 개수가 저장되도록 설정하였다. 이렇게 할 경우, 곱하기 된 무게에 대해, 기존 무게가 같은 경우와 다른 경우가 모두 썪여서 저장이 되기 때문에 문제를 풀 수가 없어진다. 이를 해결하기 위해서는 {기존 무게: 개수} 이런식으로 key-value 쌍을 넣어서 저장해야한다.

 

 

무게가 같은 경우

무게의 경우 크게 같은 경우와 다른 경우로 나눠서 생각을 해줘야한다. 같은 경우를 예시로 들어서 생각을 해보자. 100이라는 무게를 가진 사람이 4명 있을 때, 이들 간에 짝궁을 정하는 방법은 4명중 2명을 조합한 4C2=6 가지 경우이다. 즉, 같은 무게가 n명 있을 때 2명을 조합하는 방법으로 구하면된다(nC2=n*(n-1)/2)

for num,count in weights_dict.items():
    if count>1:
        answer+=count*(count-1)//2

 

 

무게가 다른 경우

무게가 다른 경우에는 거리에 따른 무게 비율을 통해 상대의 무게를 계산하고, 해당 무게의 개수 구해줘야한다. 이때, 특정 사람을 기준으로 모든 거리 비율에 대한 무게를 구해하게 되면 중복이 발생한다. 예를 들어, 특정 무게 A에 대한  2/3, 3/2를 구해서 적용할 경우, 해당 무게를 가진 사람들을 기준으로 할 때, 3/2, 2/3이 적용되어 2번 카운트가 된다. 즉, (A,B) 와 (B,A)를 모두 카운트 하는 것과 같아진다. 따라서 이를 방지하기 위해 절반의 거리 비율만 적용하여 중복을 방지한다.

for num,count in weights_dict.items():

    if num*2 in weights_dict:
        answer+=count*weights_dict[num*2]
    if num*3%2==0 and num*3//2 in weights_dict:
        answer+=count*weights_dict[num*3//2]
    if num*4%3==0 and num*4//3 in weights_dict:
        answer+=count*weights_dict[num*4//3]

 

 

시간 복잡도

weights의 무게 개수를 파악하기 위해 for문을 돌아야하므로 O(N)의 시간이 걸리며, N의 최대 개수가 1e5이므로 시간내에 동작한다

 

 

코드

from collections import Counter
def solution(weights):
    weights_dict=dict(Counter(weights));
    answer=0
    for num,count in weights_dict.items():
        if count>1:
            answer+=count*(count-1)//2
        if num*2 in weights_dict:
            answer+=count*weights_dict[num*2]
        if num*3%2==0 and num*3//2 in weights_dict:
            answer+=count*weights_dict[num*3//2]
        if num*4%3==0 and num*4//3 in weights_dict:
            answer+=count*weights_dict[num*4//3]
            
    return answer

 

 

회고

뭔가 문제는 간단해보였는데 생각할 부분이 조금씩 있었고, 그걸 풀어내는 힘이 많이 떨어진다는 느낌을 받았다..구현 부분을 추가 연습할 필요가 있다.