[LeetCode] Equal Row and Column Pairs

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

 

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:

Input: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
Output: 3
Explanation: There are 3 equal row and column pairs:

- (Row 0, Column 0): [3,1,2,2]

- (Row 2, Column 2): [2,4,2,2]

- (Row 3, Column 2): [2,4,2,2]
 

Constraints:
n == grid.length == grid[i].length
1 <= n <= 200
1 <= grid[i][j] <= 105

---

 

행과 열의 길이가 같은 이중 배열이 주어진다.

여기서 같은 순서와 값으로 구성된 같은 페어가 몇 쌍인지 구하는 문제.

이미 페어가 된 행이어도 다음 열과 같다면 별도로 카운트한다.

 

const convert = (grid) => {
    const rows = [];
    const columns = [];
    for(let i=0; i < grid.length; i++){
        let row = [];
        let column = [];
        for(let j=0; j < grid.length; j++){
            row.push(grid[i][j]);
            column.push(grid[j][i]);
        }
        rows.push(row.join("|"));
        columns.push(column.join("|"));
    }
    return { rows, columns };
}

const equalPairs = function(grid) {
    // 행 전체와 열 전체가 동일한 페어가 몇개인지 카운트
    // 일단 모든 행과 열을 구해서 join한 string을 만든다
    const {rows, columns} = convert(grid);
    let result = 0;
    for(const row of rows){
        for(const column of columns){
            if(row == column){
                result++;
            }
        }
    }
    return result;
};

 

우선은 모든 행과 열을 구해서 문자열로 만든다.

이 때 숫자는 1, 11 이런식으로도 가능하니까 join할 때 중간 구분자를 넣어준다.

그렇게 구한 rows와 columns를 가지고 for문을 더 돌려서.. 둘이 같으면 pair로 치고 카운트를 올려주고 리턴한다!

 

효율이 그렇게 나쁘진 않았는데 아주 조금 더 개선해 보자면

const equalPairs = function(grid) {
  const n = grid.length;
  const rowMap = new Map();
  let count = 0;

  for (const row of grid) {
    const key = row.join(',');
    rowMap.set(key, (rowMap.get(key) || 0) + 1);
  }

  for (let c = 0; c < n; c++) {
    const col = [];
    for (let r = 0; r < n; r++) {
      col.push(grid[r][c]);
    }
    const key = col.join(',');
    count += rowMap.get(key) || 0;
  }

  return count;
};

이렇게도 할 수 있겠다.. {}를 써도 되지만 한 번 Map을 써 봤다.

어쩌다 보니 Map을 쓸 일이 거의 없어서 익숙치 않았는데, 이번 기회에 차이점을 찾아 보니 크게 두 가지 정도 있었다.

1. map에는 키값으로 문자열이나 숫자가 아닌 다양한 타입을 넣을 수 있다.

2. 입력 순서가 유지된다.

이번 문제에 대해서는 굳이 Map이 아니어도 되긴 한다.

 

 

아무튼 저렇게 개선해도 1등만큼 빠른 것은 아니기 때문에...

1등 코드를 또 훔쳐와 본다.

var equalPairs = function(grid) {
  let pairCount = 0;
  const hashArr = [];

  // calculate hashes for rows
  for (let i = 0; i < grid.length; i++) {
    let hash = 0;
    for (let j = 0; j < grid.length; j++) {
      hash = grid[i][j] + (hash << 6) + (hash << 16) - hash
    }
    hashArr.push(hash);
  }

  //calculate hashes for columns
  for (let i = 0; i < grid.length; i++) {
    let hash = 0;
    for (let j = 0; j < grid.length; j++) {
      hash = grid[j][i] + (hash << 6) + (hash << 16) - hash
    }

    for (let k = 0; k < hashArr.length; k++) {
      if (hash === hashArr[k]) {
        pairCount++;
      }
    }
  }

  return pairCount;
};

 

이게 뭔소리야?

뭔지 몰라도 해싱을 활용해서 푼 것 같은데... 찾아보니 DJB2 라는 기법이다.

Daniel J. Bernstein이 만들어낸 해시 함수 중 두 번째 버전이라서 DJB2라고 한다.

이 다니엘이라는 사람이 이거 말고도 다양한.. 간단하고 효율적인 알고리즘을 많이 고안한 대단한 사람이다.

위 코드에서, 비트연산자에 사용한 6과 16 부분 코드는 결국 내부적으로 hash = value + 65599 * hash 가 되는데,

65599라는 숫자가 해시 분산의 품질을 높여주는 경험적 조합이라고 한다.

서로 다른 데이터가 서로 충돌이 덜 일어나도록 도와주는 계수라고 보면 된다.

https://doc.riot-os.org/group__sys__hashes__sdbm.html

sdbm이라는 어떤 데이터베이스 시스템의 해시 함수가 사용하는 계수가 바로 이 65599라고.. 오호라.. 

 

djb2에 대한 간단한 예시와 원리에 대한 건 아래 참고!

https://theartincode.stanis.me/008-djb2/#:~:text=Written%20by%20Daniel%20J.,a%20number%20that%20represents%20it.

https://youtu.be/jtMwp0FqEcg?si=mJlo4ut0hWVWvfKH

간단히 요약하면, 열과 행을 이루는 배열을 해싱처리해서 정수로 만들고,

그 정수를 비교해서 같고 다름을 구분하는 식으로 빠르게 처리했다는 뜻이다. ~.~

오늘은 문제 자체를 이해하고 푸는 것 이상으로 더 얻은 게 많았다.

새삼 세상 참 넓고 비범한 사람은 더 많다... 화이팅..