Distinct Positive Integers
서로 다른 양의 정수 a, b, c, d가 있을 때, a * b = c * d가 되게 하는 튜플 (a, b, c, d)의 개수를 리턴.
예를 들어 Input이 [2, 3, 4, 6]일 때, 해당하는 튜플은 다음과 같다.
(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)
(3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)
따라서 Output은 8
예를 들어 Input이 [1, 2, 4, 5, 10]일 때, 해당하는 튜플은 다음과 같다.
(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)
(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)
(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,5,4)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)
따라서 Output은 16
a * b, c * d가 같은 수가 나오려면 임의의 a * b를 곱한 수가 2번 이상 출현해야 한다.
즉 예를 들어 [2, 3, 4, 6]일 때 임의의 a*b를 곱한 수는 [6, 8, 12, 12, 18, 24]이며
12가 두 번 출현하였으므로 12를 구성하는 [2, 6, 3, 4]의 가능한 순열을 모두 출력하면 8개이다.
또 예를 들어 [1, 2, 4, 5, 10]일 때 임의의 a*b를 곱한 수는 [2, 4, 5, 10, 8, 10, 20, 20, 40, 50]이고
10이 두 번, 20이 두 번 출현하였으므로 각각의 수를 구성하는 4개의 숫자의 가능한 순열을 모두 출력하면 16개이다.
Defaultdict
from collections import defaultdict
어떤 딕셔너리의 기본값을 지정해주고 싶을 때 사용한다.
예를 들어, word라는 배열 속의 각 단어들의 개수를 세고 싶을 때, defaultdict(int)를 이용해서 각 딕셔너리를 자동으로 초기화할 수 있다.
from collections import defaultdict
counter = defaultdict(int)
words = ["apple", "banana", "apple", "orange", "banana", "apple"]
for word in words:
counter[word] += 1 # 자동으로 0부터 시작하여 증가
print(counter) # {'apple': 3, 'banana': 2, 'orange': 1}
튜플의 구성요소(중복 가능)의 갯수를 세고 싶을 때 유용하다.
def tupleSameProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
from collections import defaultdict
n = len(nums)
count = defaultdict(int)
res = 0
for i in range(n):
for j in range(i + 1, n):
res += 8 * count[nums[i] * nums[j]]
count[nums[i] * nums[j]] += 1
return res
count[nums[i] * nums[j]] 부분에서 defaultdict가 사전에 사용되지 않았더라면 딕셔너리가 초기화되지 않은 상태라 오류가 발생하지만,
defaultdict(int) 때문에 자동으로 0부터 시작하므로 만약에 nums[i] * nums[j] 값이 한 개만 존재한다면 res는 8*0 = 0이 더해진다.
그러나 count[nums[i] * [nums[j]]가 사전에 1이 된 상태였다면, res에 8이 더해지며 2가 된다.
만약에 count[nums[i] * [nums[j]]가 2였던 상태에서 3이 되더라도, 경우의 수는 8개씩만 늘어나므로 8*count만큼만 더해주면 된다.