23.02.17 파이썬 코딩 퀴즈#160 시소 짝꿍 (프로그래머스 스쿨)

이번 문제는 시소 짝꿍 문제이다.

시소에는 양쪽에 1명씩 총 2명이 짝을 지어서 탑승 할 수 있으며, 좌석의 위치는 중심으로 부터 2m, 3m, 4m 씩 떨어져 있다. 시소가 균형을 이루기 위해서는 탑승한 사람 무게 x 시소 축에서 좌석간의 거리 의 양 쪽 갚이 같아야 한다.

이렇게 균형을 이루는 시소 짝꿍이 몇 쌍 존재하는지 구해야 한다.

특별한 제한 사항은 없다.

첫 코드이다. 역시 weights 의 길이가 10만 이하라 그런지 시간제한에 걸린다.

시간을 개선하기 위해서는 다른 방식으로 접근이 필요하다.

먼저 기준점을 120으로 보고 120이랑 같이 시소를 탈 수 있는 사람의 몸무게를 확인해보자

(120이 기준인 이유는 2,3,4의 최소 공배수 12의 배수이기 때문이다.)

[60,80,90,120,160,180,240]으로 총 7 가지가 된다.

그 이유는 100을 2 배 했을때 같이 탈 수 있는 사람은 200/2, 200/3, 200/4 이기 때문이다.

3배, 4배도 마찬가지이다.

즉 자신의 무게에 [1/2배, 3/2배, 4/3배, 1배, 1과1/3배, 1,5배, 2배] 까지 같이 탑승이 가능하다. 이를 dict를 활용해서 작성해보자.

[예시 : [120,240,360,480] ]

초기값이 0 인 dict 를 작성하기 위해 defaultdict 라이브러리를 사용하였다.

이제 반복문을 통해 weights 를 돌며 , 각 무게별 쌍이 가능한 무게를 dict에 key 로 저장하게 된다.

이때 기본값은 0 이기 때문에 처음 들어간 i 에 의해 anwer은 값 변화가 없다.

그리고 t_w[i] 는 자신이기 때문에 값을 1 증가 시켜 준다.

그리고 t_w 에는 {60 : 0, 80 : 0, 90: 0, 120: 1, 160 : 0, 180: 0, 240 : 0} 이 쌍으로 존재하게 된다.

직역하자면 120 은 1명이 존재하고, 나머지 무게는 존재하지 않는 다는 뜻이다.

 

그 다음 240을 돌게 되는데, [ 120, 160,180,240,320,360,480] 의 key가 나온다. 이 때 120의 value는 이미 1 이기 때문에 1을 더해주게 된고, 다시 240의 value는 1을 더해준다.

 

위 방법으로 계속 진행하면 출현한 횟수 만큼 answer에 값을 증가시켜 줄 수 있다.

또한 [100,100,100,100] 같이 중복된 값들의 처리도 가능하다.

처음 나온 100은 혼자이기 때문에 쌍이 없다.

두번째 나온 100은 처음 나온 100과 쌍이 된다[t_w[100] == 1] 

세번째 나온 100은 처음 나온 100과 두번째 100과 쌍이 된다 [t_w[100]==2]