[LeetCode] 2352. Equal Row and Column Pairs

 

📌 문제 요약

주어진 n x n 크기의 정수 행렬 그리드에서 행 ri와 열 cj가 동일한 요소를 가지는 쌍 (ri, cj)의 개수를 구하라.

행과 열은 같은 순서로 동일한 값을 가져야 한다.

 

💡 풀이 포인트

• 각 행과 각 열을 완전히 동일한 순서로 비교해야 함.
• 두 배열(행과 열)을 비교할 때, 배열의 모든 요소를 하나씩 비교하는 방식으로..
• 중복되는 쌍을 세지 않도록 주의

 

✅ 풀이 방법

1. 이중 반복문으로 행과 열 비교
2. 각 행 ri와 열 cj를 k를 사용하여 일치하는지 비교
3. 일치하는 경우 카운트 +1
4. 총 카운트 반환

 

public class Solution {
    public int equalPairs(int[][] grid) {
        int n = grid.length;
        int count = 0;
        
        // 행은 고정, 열 순차적 비교
        for (int i = 0; i < n; i++) {  // 행 반복
            for (int j = 0; j < n; j++) {  // 열 반복
                boolean match = true;  // 일치하는지 확인
                // 해당 행과 열을 비교
                for (int k = 0; k < n; k++) {
                    if (grid[i][k] != grid[k][j]) {
                        match = false;  // 하나라도 다르면 일치하지 않음
                        break;
                    }
                }
                if (match) {  // 일치하면 카운트 증가
                    count++;
                }
            }
        }
        
        return count;
    }
}

 

풀이 설명

1. 첫 번째 반복문에서 행을 고르고, 두 번째 반복문에서 열을 고릅니다.
2. grid[i][k]와 grid[k][j]가 동일한지 비교
3. 행과 열이 일치하면 카운트 증가

 

시간 복잡도 : O(n^3)

• 주어진 n이 최대 200 -> 최악의 경우에도 약 8백만 번의 연산을 하므로 충분히 처리 가능