DDOING

Record my study

My code

1
2
3
4
5
6
7
8
9
10
11
12
13

import numpy as np
class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        grid_original = np.array(grid)
        grid_transpose = np.array(grid).T
        count = 0

        for i in range(len(grid_original)):
            for j in range(len(grid_transpose)):
                if np.array_equal(grid_original[i] , grid_transpose[j]):
                    count += 1

        return count

1
2

Runtime : 1504ms (beats 11.49%)   
Memory : 38.9MB (beats 5.2%)

풀이

  • numpy를 사용하여 transpose한 행렬을 저장
  • 두개의 행렬을 행만 비교하여 같은 행이 있다면 count += 1

numpy를 사용해 전치하여 풀었지만, 시간 복잡도와 공간 복잡도가 박살나있었다. 다른 풀이를 봐보니 해당 문제를 hashmap을 사용하여 풀었는데, 나는 단순히 numpy를 사용하여 어거지로 푼 느낌이 있다. solution을 보며 좋다고 느낀 아이디어가 2개가 있었는데, 하나는 rows[row] = 1 + rows.get(row,0) 이다. rows 라는 dict를 설정하여, grid의 row를 키값, 등장 횟수를 value로 저장하였다. 이때 처음 만나는 키값도 default를 정하여 오류가 나지 않도록 .get() 함수를 사용할 수 있다는 것을 알았다. 다른 하나는 나와 같이 전치를 하지만, counter를 사용하여 hashmap으로 저장한다. 이후 answer를 서로 같은 키값의 value를 곱하여 sum을 하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

import numpy as np
class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        n = len(grid)
        count = 0
        rows = {}

        for r in range(n):
            row = tuple(grid[r])
            rows[row] = 1 + rows.get(row,0)

        for c in range(n):
            col = tuple(grid[i][c] for i in range(n))
            count += rows.get(col,0)

        return count

1
2
3
4
5
6
7
8
9
10

import numpy as np
class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        tpse = Counter(zip(*grid))

        grid = Counter(map(tuple,grid))

        ans = sum(tpse[t]*grid[t] for t in tpse)

        return ans

참고