해당 문제 'Count Nice Pairs in an Array'는 nums 라는에서 'nice pair'의 수를 찾는 문제입니다. 배열 안의 두 숫자 'i'와 'j' ('i' < 'j') 가 'nice pair'로 간주될 때, "nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])" 이 성립해야 합니다. 여기서 rev(x)는 숫자 x의 자릿수를 반전시킨 결과입니다.
문제의 핵심은 각 숫자와 그 숫자의 반전된 형태의 차이를 이용하는 것입니다. 이 차이가 동일한 숫자들의 쌍이 'nice pair'를 형성합니다.
우선 코드부터 살펴보겠습니다.
class Solution(object):
def countNicePairs(self, nums):
mod = 10 ** 9 + 7
rev_nums = []
# 각 숫자를 반전시켜 새로운 배열 생성
for n in nums:
rev_nums.append(int(str(n)[::-1]))
# 원래 숫자와 반전된 숫자의 차이 계산
diff = []
for i in range(len(nums)):
a = nums[i] - rev_nums[i]
diff.append(a)
# 차이값의 빈도수 계산
frq_count = Counter(diff)
count = list(frq_count.values())
# 조합 공식을 이용하여 쌍의 수 계산
total = 0
for c in count:
total += (c*(c-1)) //2
return total % mod
코드 설명은 다음과 같습니다.
- 배열의 각 요소 반전
- 주어진 배열의 각 요소를 문자열로 변환한 다음, 문자열 슬라이싱을 이용하여 반전시킵니다.('[::-1]')
- 이 반전된 숫자들을 새로운 배열 'rev_nums'에 저장합니다.
- 차이 계산
- 원래 숫자와 반전된 숫자 간의 차이를 계산합니다. 이 차이를 'diff' 리스트에 저장합니다.
- 'diff' 리스트는 'nums[i] - rev_nums[i]' 의 결과로 구성됩니다.
- 빈도수 계산
- 'diff' 리스트에서 각 요소의 빈도수를 계산합니다. 이를 위해 'Counter' 클래스를 사용합니다.(딕셔너리를 사용해도 됩니다.)
- 빈도수는 'nice pair'의 가능한 조합 수를 계산하는 데 중요합니다.
- 쌍의 수 계산
- 각 차이값에 대해 몇 번 나타나는지를 알면, 해당 차이값을 가지는 'nice pair'의 수를 계산할 수 있습니다.
- 각 빈도수 'c'에 대해 'c * (c-1) /2 ' 를 계산하여 모든 가능한 쌍의 수를 더합니다.
- (어떻게 해서 이 공식이 나타났는지 궁금하면 아래 접은글을 확인해주세요) -- 수학 조합과 관련한 이해
-
더보기서로 다른 요소를 선택하는 경우의 수를 계산할 때, 이 공식이 사용되는 이유는 조합(combination)의 개념과 관련이 있습니다. 조합은 서로 다른 n 개의 요소 중에서 2개를 선택하는 방법을 말하는데, 이를 수학적으로 nC2 라고 할 수 있습니다.
이 공식은 n개의 요소 중 첫 번째 요소를 선택하는 n가지 방법과, 남은 n-1 개 중에서 두 번째 요소를 선택하는 n-1 가지 방법을 곱한 다음, 순서가 중요하지 않기 때문에 2로 나누어 순열(permutation)을 조합으로 변환합니다.예를 들어, n = 4 인 경우를 생각해보면, 4개의 요소 중 2개를 선택하는 방법의 수는 (4x3) / 2 로 6가지가 됩니다. 이는 첫 번째 요소를 선택하는 4가지 방법과, 남은 3가지 중 하나를 선택하는 3가지 방법을 곱한 후 2로 나누어 순서를 고려하지 않는 조합의 개수를 얻는 것입니다.
- 모듈러 연산
- 큰 숫자를 다루기 위해 최종 결과를 10**9 + 7 의 모듈러 연산합니다.
두 가지 요소 중 선택해야 하는 문제에서는 해시 테이블과 조합 공식을 생각해봅시다!
이상으로 Counter, Hash Table, 조합 공식과 관련한 1814. Count Nice Pairs in an Array 문제를 정리해봤습니다.
반응형