[LeetCode] 데카르트 곱, 해시테이블
2352. Equal Row and Column Pairs Solved Medium Topics [
](#) Companies Hint Given a 0-indexed n x n integer matrix grid, return the number of pairs *(ri, cj) such that row ri and column cj are equal*. A row and column pair is considered equal if they contain the same elements in the same order (i.e., an equal array).
Example 1:
Input: grid = [[3,2,1],[1,7,6],[2,7,7]] Output: 1 Explanation: There is 1 equal row and column pair: - (Row 2, Column 1): [2,7,7] Example 2:
- n == grid.length == grid[i].length
- 1
- 1 5
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def equalPairs(self, grid: List[List[int]]) -> int:
counter = 0
n = len(grid)
for i in range(n):
for j in range(n):
col_j = [grid[k][j] for k in range(n)]
if grid[i] == col_j:
counter += 1
return counter
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def equalPairs(self, grid: List[List[int]]) -> int:
counter = 0
n = len(grid)
# 전치행렬 만들기 (행과 열 바꾸기)
transposed = [[grid[j][i] for j in range(n)] for i in range(n)]
for i in range(n): # 각 행
for j in range(n): # 각 열 (전치행렬의 행)
if grid[i] == transposed[j]:
counter += 1
return counter
해시테이블로도 문제를 풀 수 있다.
문자열로 저장해서 할 수도 있고, 튜플로 저장해서 할 수도 있다.
문자열보단 튜플이 타입안전성 면에서, 그리고 속도 면에서 이점이다. 코드로 보기에도 깔끔하다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def equalPairs(self, grid: List[List[int]]) -> int:
from collections import Counter
# 모든 행을 문자열로 변환해서 카운트
rows = Counter(','.join(map(str, row)) for row in grid)
counter = 0
n = len(grid)
# 각 열에 대해 같은 행이 몇 개인지 확인
for j in range(n):
col_str = ','.join(str(grid[i][j]) for i in range(n))
counter += rows[col_str]
return counter
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def equalPairs(self, grid: List[List[int]]) -> int:
from collections import Counter
# 모든 행을 튜플로 변환해서 카운트
rows = Counter(tuple(row) for row in grid)
counter = 0
n = len(grid)
# 각 열에 대해 같은 행이 몇 개인지 확인
for j in range(n):
col = tuple(grid[i][j] for i in range(n))
counter += rows[col]
return counter
전치행렬을 만드는 방법, Counter를 써서 일치하는 개수를 찾는 방법은 기억해두자.
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.