[프로그래머스] 시소 짝꿍 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 가능한 시소 짝꿍의 수를 구하는 문제이다.

가능한 짝꿍의 조합을 하나하나 판별하는 것은 많은 시간이 걸린다.

하여 각 무게별로 가능한 조합인지 판별하고 해당 조합이 총 몇 쌍 나올 수 있는지 구하는 방법으로 해결하고자 하였다.

우선 동일한 무게를 가지는 사람은 서로 동일한 거리에만 앉으면 되므로 동일한 무게를 가지는 사람의 수를 세어 그중 2명을 뽑는 경우의 수를 구한다.

다른 무게를 가지는 사람들 중 서로 짝꿍이 될 수 있는 조합을 구한다.

이후 전체 인원 중 해당 조합으로 나올 수 있는 짝꿍의 수를 구하면 되는데 이는 각 무게의 사람 수를 곱하면 된다.

 

해당 방법으로 정답을 구하기 위해 먼저 각 무게별 인원수를 딕셔너리 형태로 저장해 준다.

여기서 만약 인원수가 2명 이상인 무게가 있으면 해당 인원 중 2명을 뽑는 경우의 수를 정답에 더해준다.

모든 무게별 인원수를 저장하였다면 딕셔너리에서의 키(무게)를 리스트 형태로 만들어 정렬한다.

정렬한 키를 가지고 가능한 조합을 생성한다.

오름차순으로 무게를 정렬하였으므로 서로 다른 무게가 균형을 맞추기 위해 가능한 거리 조합은 [3, 2], [4, 2], [4, 3] 뿐이다.

하여 각 조합별로 거리를 바꿔가며 앉았을 때 시소가 균형을 이룬다면 짝꿍이 될 수 있으므로 해당 조합으로 만들 수 있는 짝꿍의 수를 구해 더해주면 된다.

 

1. 중복되지 않은 무게의 가능한 조합을 구하기 위해 combinations 함수 호출 from itertools import combinations
2. 동일한 무게의 사람들 중 가능한 짝꿍의 수를 구할 때 factorial 함수를 사용하기 위한 전처리 import math
3. 각 무게별 인원수를 저장할 딕셔너리 생성한다. dic = {}
4. 각 무게를 중복 없이 호출하여 for w in set(weights)
5. 각 무게별 인원수를 딕셔너리에 저장한다. dic[w] = weights.count(w)
6. 이때 만약 인원수가 2명 이상이면 if (dic[w] >= 2)
7. 해당 무게의 전체 인원수 중 2명을 뽑는 경우의 수를 factorial 함수로 구하여 짝꿍의 수에 더한다. answer += math.factorial(dic[w]) // (math.factorial(dic[w] - 2) * 2)
8. 중복되지 않는 각 무게를 딕셔너리의 키를 활용해 구하고 오름차순으로 정렬한다. key = sorted(list(dic.keys()))
9. 서로 다른 무게별 가능한 짝꿍 조합을 구한다. pair = list(combinations(key, 2))
10. 두 사람이 앉을 수 있는 거리의 조합을 저장한다. distance = [[3, 2], [4, 2], [4, 3]]
11. 가능한 조합을 하나씩 불러오고 for p in pair
12. 가능한 거리의 조합을 하나씩 불러와 for d in distance
13. 만약 해당 조합이 짝꿍이 될 수 있으면 if (p[0] * d[0] == p[1] * d[1])
14. 전체 인원 중에서 해당 조합을 만들 수 있는 경우를 구하여 짝꿍의 수에 더한다. answer += dic[p[0]] * dic[p[1]]
15. 해당 조합에 대한 계산은 진행되었으므로 판별을 종료한다. break
16. 최종 짝꿍의 수를 반환한다. return answer

3. 소스코드

from itertools import combinations
import math

def solution(weights):
    answer = 0

    dic = {}
    for w in set(weights):
        dic[w] = weights.count(w)
        if (dic[w] >= 2):
            answer += math.factorial(dic[w]) // (math.factorial(dic[w] - 2) * 2)
        
    key = sorted(list(dic.keys()))
    pair = list(combinations(key, 2))

    distance = [[3, 2], [4, 2], [4, 3]]

    for p in pair:
        for d in distance:
            if (p[0] * d[0] == p[1] * d[1]):
                answer += dic[p[0]] * dic[p[1]]
                break
                        
    return answer