[Hash Map / Set, Medium] Equal Row and Column Pairs

https://leetcode.com/problems/equal-row-and-column-pairs/description/?envType=study-plan-v2&envId=leetcode-75

해시 문제이므로 정석적으로 푼다면 1번 풀이처럼 풀어야 할 것 같았다.

행 -> 열 순서 순회 결과와
열 -> 행 순서 순회 결과를 해시맵에 담아두고
같은 키로 찾아지는 것의 갯수를 구할 수 있다.

1 <= grid[i][j] <= 10^5 이므로 숫자마다 구분자를 두기 위해 String으로 변환함

다만 나는 이 문제에 한해서는 2번 풀이가 더 직관적인 것 같다.

1번 풀이

class Solution {
    public int equalPairs(int[][] grid) {

        int n = grid.length;
        Map<String, Integer> map = new HashMap<>();

        for(int i=0; i<n; i++){
            StringBuilder sb = new StringBuilder();
            for(int j=0; j<n; j++){
                sb.append(grid[i][j] + ";");
            }

            String key = sb.toString();
            map.put(key, map.getOrDefault(key, 0) + 1);
        }

        int cnt = 0;
        for(int j=0; j<n; j++){
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<n; i++){
                sb.append(grid[i][j] + ";");
            }
            cnt += map.getOrDefault(sb.toString(), 0);
        }
        return cnt;
    }
}

2번 풀이

• 각 grid[i][j]에서, k번 순회를 추가해 행과 열에서 다른 값이 있는지 체크
• 즉, grid[i][0~N-1]과 grid[0~N-1][j]로 행/열 기준점에서 순회 시 다른 값이 찾아진다는 것은 정답범위가 아니라는 뜻이므로 cnt 증가 안 시킴, 그 외에는 cnt 증가

class Solution {
    public int equalPairs(int[][] grid) {

        int n = grid.length;
        int cnt = 0;

        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                
                boolean isMatched = true;
                for (int k=0; k<n; k++) {
                    if (grid[i][k] != grid[k][j]) {
                        isMatched = false; 
                        break;
                    }
                }

                if (isMatched) {
                    cnt++;
                }
            }
        }

        return cnt;
    }
}