LeetCode: 1128. Number of Equivalent Dominoes

728x90

문제 

출처: LeetCode 

주어진 배열에서 도미노 쌍(domino pair)의 개수를 알아내는 문제이다. 도미노 쌍은 두 배열이 [a, b], [c, d] 주어졌을 때,  a==c & b==d || b==c & a == d를 만족하는 것을 말한다. 즉, 두 원소가 그대로 혹은 뒤집어 같으면 도미노쌍으로 정의한다. 주의할 점은 같은 원소를 비교할 수 없다. 따라서 중복 카운팅 없이 도미노쌍을 찾아야 한다. 

 

Solution 1 (Brute force) - Time Limited Error

모든 경우의 수를 탐색해보는 brute force 방법으로 먼저 코딩해 볼 수 있다. 간단한 문제이고 이중 for문으로 짜볼 수 있다. 

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        ans = 0
        N = len(dominoes)

        for i in range(N-1): 
            d1 = dominoes[i]
            for j in range(i+1,N): 
                d2 = dominoes[j]
                if d1[0] == d2[0] and d1[1] == d2[1] or d1[1] == d2[0] and d1[0] == d2[1]:
                    ans +=1 

        return ans 

하지만 이 방법은 배열이 긴 경우 time limited error (TLE)를 낸다. 따라서 다른 방법을 생각해야 한다. 

Solution 2 (using dictionary) 

두 번째로 생각할 수 있는 방법은 해시 테이블을 사용하는 것이다. 파이썬에서는 딕셔너리를 이용할 수 있다. 계획은 다음과 같다. 각 원소를 key로 만들어 이것들의 출현 횟수를 value로 하는 딕셔너리를 만드는 것이다. 이때 주의할 것은 위의 문제에서 보듯이 dominoes의 원소는 숫자나 문자가 아니라 배열이라는 것이다. 따라서 이것을 딕셔너리의 key로 지정될 수 있는 형태로 변환해야 한다는 것이다. 다음과 같은 룰로 변환하였다. 

 

for [a, b]  ------> ab if a > b  

for [a, b]  ------> ba otherwise 

 

위와 같은 방식으로 key를 저장하면 딕셔너리를 만드는 과정에서 자연스럽게 도미노쌍이 찾아지게 된다. 따라서 딕셔너리가 완성되면 values를 더하기만 하면 끝이다.  

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        counts = {} 

        for d in dominoes:
            key = min(d)+10*max(d)
            if key in counts:
                counts[key] +=1 
            else: 
                counts[key] = 1 

        return sum(c*(c-1)//2 for c in counts.values())

리턴은 중복 카운팅을 피하기 위해 combination으로 계산되었다. 따라서 개수가 한 개인 원소는 카운트되지 않는다. 

 

$$ nC_2 = \frac{n!}{2!(n-2)!} = \frac{n(n-1)}{2}$$