Leetcode - 1128. Number of Equivalent Domino Pairs

문제

크기 2배열값들이 주어진다. [1,2][2,1] 그리고 [1,2], [1,2]가 도미노 관계라고 할때, 도미노 관계인 쌍의 갯수 구하기.
https://leetcode.com/problems/number-of-equivalent-domino-pairs

Input: dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]]
Output: 3

해결 O(N)

우선 10x10 해시테이블을 생성하고 주어진 배열에서 각 요소갯수를 모두 더한다.
해당 테이블에서 세가지 경우의 수 별로 값을 calc() 해서 모두 더해주면 답이 나옴. (참고로 calc(n)는 n + (n-1) + (n - 2) + .. + 1 하는 계산임.)

1. i != j 이고 table[i][j], table[j][j] 모두 값이 있는경우
   그 두 값을 더한값 -1 을 calc()로 계산
2. table[i][j], table[j][j] 둘 중 한쪽은 값이 0인데 한쪽은 2이상인경우
   그 두 값을 더한값 -1 을 calc()로 계산
3. i == j 이고 table[i][j] 값이 2 이상인경우
   table[i][j] -1 을 calc()로 계산

가령 [[1,2],[1,2],[1,2],[2,1],[1,1],[1,1],[2,2],[2,2]] 의 경우, table[10][10]은 아래와 같이 채워진다.

• [1,2]가 3개 있으므로 경우의수 2에 해당 -> 2 + 1
• [2,1][1,2] 모두 존재하므로 3 + 1 -1 , 경우의수 1에해당 -> 2 + 1
• [1,1][2,2]가 각각 2개씩 있으므로 경우의수 1에 해당 -> 1 + 1
  모두 더하면 답은 8

0 0 0 0 0 0 0 0 0 0 
0 2 3 0 0 0 0 0 0 0 
0 1 2 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 

int calc(int val)
{
    int ret = 0;
    for (int i = val; i > 0; i--)
        ret += i;
    return ret;
}

int numEquivDominoPairs(int** dominoes, int dominoesSize, int* dominoesColSize){
    int ret = 0;
    int table[10][10] = {0};
    for (int i = 0; i < dominoesSize; i++) {
        table[dominoes[i][0]][dominoes[i][1]]++;
    }
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if ((table[i][j] && table[j][i] && i != j) ||
                (table[i][j] ==0 && table[j][i] > 1) ||
                (table[j][i] ==0 && table[i][j] > 1)) {
                ret += calc(table[i][j] + table[j][i] - 1);
                table[i][j] = 0;
                table[j][i] = 0;
            } else if (i == j && table[i][j] > 1) {
                ret += calc(table[i][j] - 1);
                table[i][j] = 0;
            }
        }
    }
    return ret;   
}