[Leetcode] 1128번

문제 해석

도미노가 리스트 형식으로 주어진다.
각 원소는 두 개의 원소를 가진 리스트.
이 때 각 원소끼리 동일한 위치의 요소들끼리 같거나 교차된 위치의 요소들끼리 같으면
그 원소 두 개는 'equivalent'하다고 한다.
equivalent 한 원소 쌍을 구하라.

오답

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        count = 0
        for i in range(len(dominoes)):
            for j in range(len(dominoes)):
                if i != j and dominoes[i][0] == dominoes[j][0] and dominoes[i][1] == dominoes[j][1]:
                    count += 1
                elif i != j and dominoes[i][0] == dominoes[j][1] and dominoes[i][1] == dominoes[j][0]:
                    count += 1
        return int(count/2)

일단 자기 자신과는 비교하면 안되니까 i != j 조건 걸어주고, if문으로 equivalent 조건을 걸어 주었습니다.

마지막에 쌍이 중복되서 계산되므로 2로 나눠줬습니다.

time limited로 틀렸습니다.

1 <= dominoes.length <= 4 * 104

도미노의 갯수가 4만개까지 주어질 수 있는데 이중 for문을 쓰게 되면 시간 복잡도가 O(N²)이 되면서 최대 16억번 연산이 필요합니다. -> 현실적으로 불가...

그래서 카운팅 기법 (해시맵) 을 써서 O(N) 으로 줄여야 합니다.

도미노 쌍 (a,b)는 (a,b)나 (b,a)가 같다고 했으니까,
항상 min(a,b)*10 + max(a,b) 같은 정규화된 숫자로 치환해서 같은 키로 카운트하면 됩니다.

정답

from collections import Counter
class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        counter = Counter()
        for a, b in dominoes:
            key = tuple(sorted((a, b)))  # (a,b)나 (b,a) 둘 다 동일하게
            counter[key] += 1
        
        count = 0
        for freq in counter.values():
            count += freq * (freq - 1) // 2  # nC2 계산
        
        return count

1-linear-solution

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        return sum(f*(f-1)//2 for f in Counter(min(d0*10+d1, d1*10+d0) for d0, d1 in dominoes).values())

min(d0*10+d1, d1*10+d0) for d0, d1 in dominoes
➡️ 각 도미노들의 원소를 숫자로 만들어줍니다. (ex. [1,2] -> 12, 21)

[1,2] -> (12,21) 중 최솟값 12를 선택합니다.

그럼 [1,2]도 [2,1]도 12로 계산되고 이렇게 숫자 위치만 반대로 된 원소들끼리 같이 딕셔너리로 묶여버립니다.

Counter()은 파이썬 collections 모듈에 포함된 클래스로,
리스트나 이터러블에서 각 항목이 몇 번 등장했는지 세어주는 딕셔너리 같은 자료구조입니다.

from collections import Counter

예를 들면

dominoes = [[1,2],[2,1],[1,2],[3,4]]
→ 정규화된 값 = [12, 12, 12, 34]
→ Counter = {12: 3, 34: 1}

이런 식으로 묶어줍니다.

그 다음 .values()로 항목 등장횟수만 들고 와서, 각 등장횟수마다
가능한 쌍의 조합의 갯수를 계산해줍니다.

동일한 도미노가 f개 있다면, 이 중에서 서로 다른 2개를 뽑아 쌍을 만들 수 있습니다.

f*(f-1)//2는 같은 도미노가 f개 있을 때, 서로 다른 두 개를 뽑아 만드는 모든 가능한 쌍의 개수를 의미합니다.

한 줄짜리 코드는 리트코드의 Solution 부분을 참고했습니다.
간결한 코드를 만드려면 그 만큼 수학적 지식도 많아야 할 것 같네요.