728x90
# 조건
- 어느 공원 놀이터에는 시소가 하나 설치되어 있습니다.
- 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.
- 이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다.
- 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.
- 사람들의 몸무게 목록
weights
이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.
제한 사항
- 2 ≤
weights
의 길이 ≤ 100,000 - 100 ≤
weights
[i] ≤ 1,000- 몸무게 단위는 N(뉴턴)으로 주어집니다.
- 몸무게는 모두 정수입니다.
입출력 예
- weights = [100, 180, 360, 100, 270]
- result = 4
- {100, 100} 은 서로 같은 거리에 마주보고 앉으면 균형을 이룹니다.
- {180, 360} 은 각각 4(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
- {180, 270} 은 각각 3(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
- {270, 360} 은 각각 4(m), 3(m) 거리에 마주보고 앉으면 균형을 이룹니다.
# 접근 방법
- 주어지는 weight 모두를 순회하면 100,000^2이 될 수 있기에 시간 초과가 발생한다.
- 하지만 주어지는 몸무게 단위는 100 이상 1000이하이므로 나올 수 있는 몸무게 표본은 901개이므로, 입력을 받은 후 dictionary에 각 몸무게마다 사람 수를 기록해준다.
- 이후, index 값을 사용하기 위하여 sorted를 이용하여 (key, value) 값으로 만들어 준다.
- 몸무게를 순회하며 해당 몸무게를 가진 사람이 1명 이상인 경우 4C2 만큼 더해준다.
- 100kg이 4명이라면 시소에 앉을 수 있는 경우의 수는
- 4 * 3 // 2 가 된다.
- 또한, 다른 몸무게와 비교하며 시소 짝꿍이 될 수 있는지 보기 위하여 x2, x3, x4 한 값을 temp1과 temp2 리스트에 저장해준다.
- temp1의 값이 temp2에 들어있다면 각 사람 수만큼 곱한 값을 answer에 더해준다.
- 100이 3명 200이 2명인 경우, 나올 수 있는 조합의 수는 2 x 3 = 6 개가 된다.
from collections import defaultdict
def solution(weights):
values = defaultdict(int)
for i in weights:
values[i] += 1
answer = 0
val = sorted(values.items())
leng = len(val)
for i in range(leng):
n_weight = val[i][0]
n_count = val[i][1]
temp1 = [n_weight * 2, n_weight * 3, n_weight * 4]
if n_count > 1:
answer += n_count * (n_count -1) // 2
for j in range(i+1, leng):
r_wieght = val[j][0]
r_count = val[j][1]
temp2 = [r_wieght *2, r_wieght* 3, r_wieght * 4]
for k in temp1:
if k in temp2:
answer += n_count * r_count
break
return answer
728x90
'ALGORITHM > Greedy' 카테고리의 다른 글
[프로그래머스 Lv 3] 파이썬 - 단속 카메라 (0) | 2023.07.20 |
---|---|
[프로그래머스 Lv2] 파이썬 - 광물 캐기 (0) | 2023.07.07 |
[프로그래머스] 파이썬 - 점 찍기 (0) | 2023.05.23 |
[프로그래머스] 파이썬 - 택배 배달과 수거하기 (0) | 2023.05.22 |
[백준 14939번] 파이썬 - 불끄기 (0) | 2023.05.09 |