알고리즘 코드카타 121 - 시소짝꿍

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(뉴턴)으로 주어집니다.
몸무게는 모두 정수입니다.

 

 

시소가 균형을 이루는 경우의 수를 구하는 문제, 생각 외로 시간이 오래 걸렸다.

 

def solution(weights):
    answer = 0
    
    ratio = (2/3, 3/4, 2/4, 3/2, 4/3, 4/2)
            
    return answer

 

우선 시소의 거리에 따른 무게의 비율을 ratio에 저장한다.

 

# def solution(weights):
#     answer = 0
    
#     ratio = [2/3, 3/4, 2/4, 3/2, 4/3, 4/2]
    
    count_weights = {key:0 for key in weights}
    for weight in weights:
        count_weights[weight] += 1
            
#     return answer

 

count_weights라는 딕셔너리를 생성한다. 해당 딕셔너리는 weights의 모든 원소를 중복없이 key값으로 가지며 value값으로 weights의 각 원소의 갯수를 입력한다. 각 체중에 해당하는 사람이 몇명있는지 확인하기 위함이다.

# def solution(weights):
#     answer = 0
    
#     ratio = [2/3, 3/4, 2/4, 3/2, 4/3, 4/2]
    
#     count_weights = {key:0 for key in weights}
#     for weight in weights:
#         count_weights[weight] += 1
        
    for weight_1 in count_weights:
        for weight_2 in count_weights:
            if weight_1 < weight_2:

            elif weight_1 == weight_2:
                answer += count_weights[weight_1] * (count_weights[weight_2] - 1) // 2
            
#     return answer

 

이중 for문으로 count_weights의 모든 key값(중복을 제외한 weights의 값)의 조합을 검사한다.

두 값이 같은 경우, weights안에 해당 값이 count_weights의 해당 key의 value만큼 존재한다는 의미이므로 해당 값에서 시소가 평형을 이룰 수 있는 모든 조합의 수는 n * (n-1) // 2 가 된다. 자기 자신을 제외하고 순서를 고려하지 않아야하기 때문이다.

 

# def solution(weights):
#     answer = 0
    
#     ratio = [2/3, 3/4, 2/4, 3/2, 4/3, 4/2]
    
#     count_weights = {key:0 for key in weights}
#     for weight in weights:
#         count_weights[weight] += 1
        
#     for weight_1 in count_weights:
#         for weight_2 in count_weights:
#             if weight_1 < weight_2:
                weight = weight_1 / weight_2
                if weight in ratio:
                    answer += count_weights[weight_1] * count_weights[weight_2]
#             elif weight_1 == weight_2:
#                 answer += count_weights[weight_1] * (count_weights[weight_2] - 1) // 2
            
#     return answer

 

마지막으로 weight_1 < weight_2인 경우를 고려한다. 순서를 고려하지 않으므로 중복탐색을 방지하기 위해서 weight_1 > weight_2인 경우는 고려하지 않는다.

이때. 두 수를 나눈 비율 weight가 시소의 무게에 따른 비율 ratio 안에 존재할 경우 해당 조합이 유효한 조합이므로 해당 조합에서 고려 가능한 모든 조합 n * k를 answer에 더해주면 원하는 결과를 출력할 수 있다.

 

 

def solution(weights):
    answer = 0
    
    ratio = [2/3, 3/4, 2/4, 3/2, 4/3, 4/2]
    
    count_weights = {key:0 for key in weights}
    for weight in weights:
        count_weights[weight] += 1
        
    for weight_1 in count_weights:
        for weight_2 in count_weights:
            if weight_1 < weight_2:
                weight = weight_1 / weight_2
                if weight in ratio:
                    answer += count_weights[weight_1] * count_weights[weight_2]
            elif weight_1 == weight_2:
                answer += count_weights[weight_1] * (count_weights[weight_2] - 1) // 2
            
    return answer

 

완료