[TIL] 동일한 행과 열 찾기

문제

2352. Equal Row and Column Pairs
2차원 배열 grid가 주어지고 행과 열의 쌍이 몇개인지 찾는 문제이다.

어디서 막혔는가?

행은 grid로 주어지므로 열배열을 생성해서 비교하려고 했다. 이중 for 문을 도니 시간초과가 떴다.

const map = new Map();
const columns = new Array(grid.length).fill("")

for (let i = 0; i < grid.length; i++) {
     const str = grid[i].join("");
     map.set(str, map.get(str) + 1 || 1)
 }

// columns 배열 추출?해서 비교하려고 했는데 시간초과.

솔루션

• 각 열을 문자열(key)로 변환해서 Map에 저장

• 각 행도 같은 방식으로 문자열로 만들고 Map에서 조회

이렇게 하면 이중 반복 없이 해결!🤓

function equalPairs(grid) {
  const n = grid.length;
  const colMap = new Map();

  // 열들을 문자열로 저장
  for (let j = 0; j < n; j++) {
    const col = [];
    for (let i = 0; i < n; i++) {
      col.push(grid[i][j]);
    }
    const colKey = col.join(',');
    colMap.set(colKey, (colMap.get(colKey) ?? 0) + 1);
  }

  // 각 행을 문자열로 만들어서 colMap에 있는지 확인
  let result = 0;
  for (let i = 0; i < n; i++) {
    const rowKey = grid[i].join(',');
    result += colMap.get(rowKey) ?? 0;
  }

  return result;
}