본문으로 건너뛰기

1128 - Number of Equivalent Domino Pairs

info

풀이 키워드​

스포주의

해시 조합


풀이 코드​

info
  • 메모리: 53100 KB
  • 시간: 2 ms
class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        int[] hash = new int[100];
        for (int[] d : dominoes)
            ++hash[d[0] > d[1] ? d[1]*10+d[0] : d[0]*10+d[1]];
        int ans = 0;
        for (int i = 11; i < 100; ++i)
            if (hash[i] > 1) ans += hash[i]*(hash[i]-1)/2; // nC2
        return ans;
    }
}

풀이 해설​

도미노 값 범위가 1~9 밖에 안되기 때문에, 정수형으로 해싱 처리가 가능한 문제이다.

d[0] > d[1] ? d[1]*10+d[0] : d[0]*10+d[1]

느려터진 HashMap 컬렉션을 사용하지 않고, 배열의 인덱스를 해시로 사용해서 상단과 같이 key를 계산하고 집계했다.

예를 들어, {1, 2} 도미노와 {2, 1} 도미노는 모두 hash[12]에 집계된다.


모두 집계했다면 배열을 스캔해서 2개씩 뽑아 조합할 수 있는 경우의 수를 합산해주면 된다.

조합 공식을 사용해도 되고, hash에 +1 하려 할 때마다 가산하기 전의 hash값을 ans에 누적해줘도 된다.


메모​

  • 문자열 처리가 필요 없다면 무조건 정수형으로 처리하는 것이 성능적으로 완전 이득이다.