[프로그래머스] 시소 짝꿍 (Python) - combinations (optional)
문제 설명
어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.
이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.
사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.
제한 사항
- 2 ≤ weights의 길이 ≤ 100,000
- 100 ≤ weights[i] ≤ 1,000
- 몸무게 단위는 N(뉴턴)으로 주어집니다.
- 몸무게는 모두 정수입니다.
입출력 예
| weights | result |
| [100,180,360,100,270] | 4 |
입출력 예 설명
{100, 100} 은 서로 같은 거리에 마주보고 앉으면 균형을 이룹니다.
{180, 360} 은 각각 4(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
{180, 270} 은 각각 3(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
{270, 360} 은 각각 4(m), 3(m) 거리에 마주보고 앉으면 균형을 이룹니다.
풀이 1
from collections import Counter
def solution(weights):
partners = 0
# 같은 값 쌍 구하기 (*1)
w_count = Counter(weights)
for w, v in w_count.items():
partners += v*(v-1)//2
# 다른 값 쌍 구하기 (*2, *3, *4)
w_set = set(weights)
ratio = [2/3, 2/4, 3/4] # 3/2, 4/2, 4/3 은 고려하지 않으므로 (100,200) (200,100) 이런 중복이 있을 염려 없음.
for w in w_set:
for r in ratio:
if w*r in w_set:
partners += w_count[w] * w_count[w*r] # (w 값의 개수) * (w*r 값의 개수)
return partners많은 실패를 거친 풀이..
문제를 제대로 이해하지 못해서 바보같이 뺑뻉 돌았던 ;(
생각해보면 이걸 왜 못 풀고 있었지? 싶다.
구글링의 힘을 빌려 푼 문제 ........................... 아쉬워요
*실패했던 풀이들:
1) 이중 반복문으로 확인하기 - 시간초과
2) 이중 반복문은 활용 안했지만..
2-1) ratio를 2/3, 2/4, 3/4 만 확인해야 하는데, 1/2, 1/3, 1/4 까지 확인하고 있었다는 점....
한 사람은 가만히 있어도 되는 줄 알았잖아 난...- 실패
2-2) 같은 몸무게인 사람들 처리를 미리 안해줬던 것 .... 아득바득 같이 처리하려고 했음 - 실패
+)
기존에 생각해냈던 이중 반복문을 안쓰던 풀이가 있었는데 ...
100이랑 200이 있다고 하면 각 값에 대해 *1 *2 *3 *4 인 값을 dict에 추가하고 value로 값을 넣어서
100: [100]
200: [100, 200]
300: [100]
400: [100, 200]
600: [200]
이런 모양새가 되는 방식을 고려했었는데요....
이후 저걸 세어 줄 생각을 하니까 갑자기 머리가 아프고 복잡해서 돌아섰다.. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
생각해보니 같은 몸무게인 사람들만 미리 처리했었다면 충분히 해볼만한 풀이였던 것 같아요... ?
... 해서 다시 또 풀어봤습니다
풀이 2 (combinations 활용)
from collections import Counter
from itertools import combinations
def solution(weights):
partners = 0
# 같은 값 쌍 구하기 (*1)
w_count = Counter(weights)
for w, v in w_count.items():
partners += v*(v-1)//2
# 다른 값 쌍 구하기 (*2, *3, *4)
# 1. A에 2,3,4 곱한 값들을 key로, A를 value로 추가
# (ex. 400: [100,200] )
w_set = set(weights)
w_dict = {}
for w in w_set:
for i in [2,3,4]:
w_dict[w*i] = w_dict.get(w*i,[])
w_dict[w*i].append(w)
# 2. value들 중 2개 이상의 값을 가진 경우 조합을 통해 파트너 리스트에 추가
# (ex. 600: [150, 200, 300] ==> [150, 200], [200, 300], [150, 300])
partners_list = []
for w in w_dict.values():
if len(w)>1:
combi = combinations(w,2)
[partners_list.append(list(x)) for x in combi]
# 3. 파트너 리스트에 있는 값들의 count를 곱해서 결과에 추가 (2개, 3개 있는 경우 경우의 수는 2*3개가 가능)
for p in partners_list:
partners += w_count[p[0]] * w_count[p[1]]
return partners같은 값을 미리 처리했다면 내가 생각해냈던 기존 방식으로 풀 수 있을거였다는 생각으로 한 번 풀어보았다...
값은 값만 미리 처리했었다면 구글링 없이 풀 수 있었을텐데!! 너무 아쉬워
정답에 다가가는 방식은 괜찮았지만 같은 값 미리 처리 안함 + ratio 1/2 1/3 1/4 까지 고려함 이 실패의 큰 원인이었던 걸로 판명 났다 이 바보 ~!
그래도 많이 배운 문제!
