프로그래머스 - 시소 짝꿍

각 자리에 앉으면 토크가 늘어나서 어떤 사람이 다른 사람과 재밌게 놀 수 있는 짝을 찾는 문제

 

토크는 그냥 쉽게 말하면 몸무게 * 시소 중심으로부터의 거리이다.

 

조건을 보면 weights가 최대 100,000이다.. 이런거 이중 for문으로 완탐돌리면 무조건 시간초과남!

시간복잡도 O(n)인 방법을 찾아야 한다.

 

그건 바로 몸무게 배열을 만드는 거다.

몸무게는 한정되어 있고 최대 1000까지이니까 몸무게를 index로 갖는 배열 형태로 만들어도 괜찮은 수준이다.

 

문제는 이렇게 몸무게에 대한 정보를 배열에 매핑(표시)해도 생각해야할 것이 있다.

1. 몸무게 같은 사람들은 nC2의 조합이다.

-> 2명인 경우 짝꿍이 될 수 있는 경우의 수는 1.

-> 3명인 경우 짝꿍이 될 수 있는 경우의 수는 3.

-> 10명인 경우 45

 

2. 같은 몸무게 군에서 다른 몸무게 군과 짝꿍이 될 수 있는 사람들은 서로 곱해야 한다.

-> 100이 2명, 300이 3명인 경우

100 한명이 300 3명과 한명씩 짝꿍이 될 수도 있고 다른 100한명이 300 3명과 한명씩 짝꿍이 될 수 있다.

 

3. list를 순회할 때 몸무게에 대한 연산을 하게 되는데 연산된 몸무게가 1000을 벗어나선 안된다.

 

 

풀이

1. 몸무게가 인덱스인 길이가 총 1001인 배열 선언

2. weights를 한번 순회하며 해당 몸무게의 수를 1씩 증가

3. 매핑된 몸무게 배열을 순회

4. 만약 해당 몸무게를 가진 사람이 존재하다면

4-1. 만약 해당 몸무게를 가진 사람이 여러명 이라면 조합처리를 하고 answer에 더해줌.

4-2. 몸무게가 2배인 사람들에 대한 처리 (4m 2m에 앉는 경우)

4-3. 몸무게가 3/2배인 사람들에 대한 처리 (3m 2m에 앉는 경우)

4-4. 몸무게가 4/3배인 사람들에 대한 처리 (4m 3m에 앉는 경우)

 

def solution(weights):
    answer = 0
    weight_list = list(0 for i in range(1001))
    
    for weight in weights:
        weight_list[weight] += 1
    
    for index in range(1001):
        if weight_list[index]:
            if weight_list[index] > 1:
                answer += weight_list[index] * (weight_list[index] - 1) // 2
            if index * 2 < 1001 and weight_list[index * 2]:
                answer += weight_list[index * 2] * weight_list[index]
            if index % 2 == 0 and index * 3 // 2 < 1001 and weight_list[index * 3 // 2]:
                answer += weight_list[index * 3 // 2] * weight_list[index]
            if index % 3 == 0 and index * 4 // 3 < 1001 and weight_list[index * 4 // 3]:
                answer += weight_list[index * 4 // 3] * weight_list[index]
                
    
    return answer