📖 연습문제 > 시소 짝꿍
📖What I thought
- 시소 짝꿍이 될 수 있는 경우를 생각해보자
- 2a= 2b 3a=3b 4a=4b → 둘의 무게가 같은 경우기 때문에 모두 똑같은 케이스 즉, 무게 비율이 1:1 인 경우
- 같은 원리로 2a=3b인 경우는 무게 비율이 2:3인 경우
- 2a = 4b → 무게 비율이 2:4(1:2)
- 3a=4b → 무게 비율이 3:4 (처음 시도)반복문으로 다 돌면서 조건문으로 각 비율만큼 곱해서 있는지 확인해보장~~ → 개같이 멸망 시간 초과 엔딩 근데 당연함 10^5*10^5임;;
- 2중 for문은 절대 안 돼 반복문을 한 번만 돌 수 있는 방법은? 모든 값에 대해 비교가 아니라 가능한 경우만 체크할 수 있는 방법은 바로바로…
- 한 무게에 대해서 가능한 비율만큼을 곱한 무게가 있는지 확인하고 그 무게의 개수를 곱해줘
- 즉, 존재하는 무게와 그 무게를 가진 사람의 수가 중요하다 → key:value를 활용해서 저장하자 → 카운터라는 좋은 모듈이 있음
- 이 카운터객체를 반복문 싹 돌아주면 for문으로 반복 가능 반복문 안에선 다음과 같은 과정을 거침
- 카운터 객체에 value가 2이상인 경우 → 1:1 비율이 존재하는 경우임 그러면 그 개수 중에서 순서 상관없이 2명 뽑으면 시소 짝꿍 하나 탄생 == 조합 식 n(n-1)//2
- 1:2 2:3 3:4 비율인 경우들은 각각 그만큼 곱해준다음 그 값에 해당하는 무게가 존재하면 ? 존재하는 개수만큼 현재 무게 개수와 곱해줌
→ 즉, 일단 모든 경우를 다 비율만큼 곱해서 확인하는 게 아니라, 먼저 각 비율에 해당하는 값을 구해보고 이 값이 있는지를 체크한 다음 그 개수를 기준 무게의 개수와 곱해줘
📖풀이
📎구현
from collections import Counter
def solution(weights):
pair = 0
counts = Counter(weights)
for weight, count in counts.items():
# 1:1
if count >= 2:
pair += count*(count-1)//2
#2:4(1:2)
if weight * 2 in counts:
pair += count * counts[weight * 2]
#2:3
if weight * 2/3 in counts:
pair += count * counts[weight * 2/3]
#3:4
if weight * 3/4 in counts:
pair += count * counts[weight * 3/4]
return pair📖What I learned
- 딕셔너리를 in 연산자로 비교한다면 해당key가 딕셔너리 안에 있는지 조사 → 굳이 dic.keys()해서 비교하지 않아도 된다!!
- 바보같이 시간을 카운터 객체로 열심히 줄여놓고 무게가 있는지 없는지를
weights리스트에서 비교했었다 ;; 카운터는 딕셔너리 + 겹치는 무게는 1개로 통일돼서 value로 카운트 됐으니까 당연히 카운터로 존재유무 파악하는 게 훠어어어얼씬 빠름