도미노 목록이 주어졌다고 가정해 보겠습니다. 각 도미노는 두 개의 숫자로 구성되며, 두 도미노 D[i] = [a, b]와 D[j] = [c, d]는 a = c이고 b = d이거나 a = d이고 b = c일 때 서로 동등하다고 간주합니다. 즉, 숫자의 순서만 바뀐 도미노는 뒤집혀도 같은 것으로 취급됩니다.
우리가 구해야 하는 것은 0 <= i < j < 도미노 목록의 길이를 만족하는 모든 인덱스 쌍 (i, j) 중에서 D[i]와 D[j]가 동등한 쌍의 개수입니다.
예를 들어 도미노 목록이 [[1, 2], [2, 1], [3, 4], [6, 5]]라면, [1, 2]와 [2, 1]만 서로 동등하므로 출력은 1이 됩니다.
문제 해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- answer를 0으로 초기화합니다.
- 도미노 목록의 각 쌍 p에 대해 다음을 수행합니다.
- 쌍 p를 오름차순으로 정렬합니다. 이렇게 하면 [1, 2]와 [2, 1]이 모두 (1, 2)로 통일됩니다.
- 정렬된 쌍을 키로 사용하여 각 도미노의 등장 빈도를 딕셔너리 D에 저장합니다.
- D의 값(빈도) b마다 다음을 더합니다.
- answer := answer + (b × (b − 1)) / 2
- answer를 반환합니다.
여기서 핵심 아이디어는 조합 공식입니다. 동일한 도미노가 b개 있다면, 이중에서 2개를 선택하는 경우의 수는 bC2 = b × (b − 1) / 2이기 때문입니다. 정렬과 해시맵(딕셔너리)을 활용하면 O(n) 시간 복잡도로 문제를 효율적으로 해결할 수 있습니다.
구현 예제
아래 파이썬 코드를 통해 더 잘 이해해 보겠습니다.
class Solution(object):
def numEquivDominoPairs(self, dominoes):
d = {}
ans = 0
for i in dominoes:
i.sort()
i = tuple(i)
if i not in d:
d[i] = 1
else:
d[i] += 1
for b in d.values():
ans += ((b * (b - 1)) // 2)
return ans
ob1 = Solution()
print(ob1.numEquivDominoPairs([[1,2],[2,1],[3,4],[5,6],[4,3]]))입력
[[1,2],[2,1],[3,4],[5,6],[4,3]]
출력
2
결과 설명
위 예제에서 [1, 2]와 [2, 1]이 첫 번째 동등 쌍을 이루고, [3, 4]와 [4, 3]이 두 번째 동등 쌍을 이룹니다. 따라서 동등한 도미노 쌍의 총 개수는 2가 됩니다.