문제 링크
풀이
길이가 10만이기 때문에 완탐으로 하면 시간초과가 난다.
같은 값이 중복으로 여러 개 있을 수 있고 하나의 값이 가질 수 있는 짝꿍의 개수도 정해져 있기 때문에 Counter를 사용해 각각의 개수를 키 값으로 갖는 딕셔너리를 만들어준다.
이제 각 딕셔너리의 키 값을 돌면서 하나의 값이 가질 수 있는 가능한 값들이 있는지 확인하고 그 값들을 딕셔너리에서 찾아서 더해주면 된다. 2, 3, 4를 곱한다음에 그 값들에 대해서 2,3,4로 다시 나눠주면 가능한 값을 구할 수 있다. 단, 이 중에서 2/2 인 경우나 3/3, *4/4의 경우 등 같은 값을 곱하고 나누는 경우는 무조건 자기 자신이 나오게 된다.
180의 경우 가능한 숫자는 90, 120, 135, 180, 240, 270, 360이다. 이 중에서 리스트에 존재하는 값은 180, 270, 360이며, 180은 자기 자신이므로 개수에서 1을 제외해야 한다. 매번 같은 값들에 대해서 자기 자신과 같은지 아닌지를 판별하고 1을 제외하는 것은 쓸모없는 연산이 계속 반복될 수 있다. 다른 값들에 대해 다 구해준 다음에 자기 자신의 개수에서 -1을 제외한 값을 한 번에 더해주는 게 더 빠르다.
처음에는 중복값이 있을 거라고 생각하고 pair를 통해 중복 값을 제거하고 구했지만, 생각해보니 중복값이 있을 수가 없었다. 두 개의 코드는 시간 자체는 거의 비슷하다.
중복 값을 고려하고 set()을 사용
def solution(weights):
answer = 0
weight = Counter(weights)
def balance(n):
pair = set()
for x in (n*2/3, n*2/4, n*3/2, n*3/4, n*4/2, n*4/3):
if weight[x]:
pair.add(x)
people = sum([weight[x] for x in list(pair)]) + (weight[n]-1)
return weight[n] * people
for key in weight:
answer += balance(key)
return answer//2
from collections import Counter
중복 값 없기 때문에 people를 바로 구해줘도 됨
def solution(weights):
answer = 0
weight = Counter(weights)
print('weight', weight)
def balance(n):
people = 0
for x in (n*2/3, n*2/4, n*3/2, n*3/4, n*4/2, n*4/3):
if weight[x]:
people += weight[x]
people += (weight[n]-1)
return weight[n] * people
for key in weight:
print(balance(key))
answer += balance(key)
return answer//2
from collections import Counter
백준의 머리 톡톡풀이에서 아이디어를 얻었다
