[LeetCode] Valid Sudoku

🧑‍💻 언어 및 제출 결과

• 사용 언어: JavaScript
• 통과 여부: ✅

🧠 풀이 설명

 

행, 열, 3×3 박스별 Set 배열 생성. Array.from으로 9개 Set을 가진 배열 3개를 한 번에 생성

const [rows, columns, boxes] = Array.from({ length: 3 }, () => Array.from({ length: 9 }, () => new Set()));

 

이중 반복문으로 9×9 보드 탐색. 빈 칸(".")은 continue로 건너뜀. 현재 위치의 3×3 박스 인덱스 계산

const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);

 

각 숫자가 행, 열, 박스 Set에 있는지 확인. 중복 시 false 반환. 없으면 Set에 추가

if (rows[i].has(num) || columns[j].has(num) || boxes[boxIndex].has(num)) {
  return false;
}

 

행, 열, 3×3 박스에도 중복 숫자가 없으면 유효한 스도쿠니까 true 반환

 

전체코드

/**
 * @param {character[][]} board
 * @return {boolean}
 */
const isValidSudoku = board => {
  const [rows, columns, boxes] = Array.from({ length: 3 }, () => Array.from({ length: 9 }, () => new Set()));

  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const num = board[i][j];
      const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);

      if (num === ".") continue;

      if (rows[i].has(num) || columns[j].has(num) || boxes[boxIndex].has(num)) {
        return false;
      }

      rows[i].add(num);
      columns[j].add(num);
      boxes[boxIndex].add(num);
    }
  }
  return true;
};

📊 시간/공간 복잡도

• 시간 복잡도: O(1) - 9×9 고정 크기
• 공간 복잡도: O(1) - 최대 81개 숫자 저장

📝 추가 설명 (선택)

번외

예전에 베이직한 9×9가 아닌 12×12나 사무라이 스도쿠 등등 만들다 포기한 적이 있었습니당.
그래서 유동적인 스도쿠를 검증 하는 것도 재밌을 거 같아 한번 짜봤습니다

 번외
 예시: 12×12 스도쿠, 4×3 박스 (가로4칸 × 세로3칸)
 boxWidth = 4, boxHeight = 3

 보드 구조:
     j: 0  1  2  3 | 4  5  6  7 | 8  9 10 11
 i:0    [   박스0   |   박스1   |   박스2   ]
   1    [          |          |          ]
   2    [          |          |          ]
   ───  ───────────┼──────────┼──────────
   3    [   박스3   |   박스4   |   박스5   ]
   4    [          |          |          ]
   5    [          |          |          ]
   ───  ───────────┼──────────┼──────────
   6    [   박스6   |   박스7   |   박스8   ]
   7    [          |          |          ]
   8    [          |          |          ]
   ───  ───────────┼──────────┼──────────
   9    [   박스9   |  박스10   |  박스11   ]
  10    [          |          |          ]
  11    [          |          |          ]

 ────────────────────────────────────────────────────────────
 j (열) 나누기 - Math.floor(j / boxWidth):
 ─────────────────────────────────────────────────────────────
 j = 0,1,2,3    → Math.floor(j/4) = 0  (박스 열 0)
 j = 4,5,6,7    → Math.floor(j/4) = 1  (박스 열 1)
 j = 8,9,10,11  → Math.floor(j/4) = 2  (박스 열 2)

 ─────────────────────────────────────────────────────────────
 i (행) 나누기 - Math.floor(i / boxHeight):
 ─────────────────────────────────────────────────────────────
 i = 0,1,2      → Math.floor(i/3) = 0  (박스 행 0)
 i = 3,4,5      → Math.floor(i/3) = 1  (박스 행 1)
 i = 6,7,8      → Math.floor(i/3) = 2  (박스 행 2)
 i = 9,10,11    → Math.floor(i/3) = 3  (박스 행 3)

 ─────────────────────────────────────────────────────────────
 최종 박스 인덱스 계산:
 ─────────────────────────────────────────────────────────────
 boxIndex = boxRow * boxesPerRow + boxCol
 boxesPerRow = 12 / 4 = 3 (한 행에 3개 박스)

 예시:
 • (1,5)  → boxRow=0, boxCol=1 → 0*3+1 = 박스 1
 • (4,8)  → boxRow=1, boxCol=2 → 1*3+2 = 박스 5
 • (10,6) → boxRow=3, boxCol=1 → 3*3+1 = 박스 10 

const isValidSudoku = (board, boxWidth = 3, boxHeight = 3) => {
  const boardSize = board.length;
  const boxesPerRow = boardSize / boxWidth;

  const [rows, columns, boxes] = Array.from({ length: boxHeight }, () =>
    Array.from({ length: boardSize }, () => new Set())
  );
  for (let i = 0; i < boardSize; i++) {
    for (let j = 0; j < boardSize; j++) {
      const num = board[i][j];
      const boxRow = Math.floor(i / boxHeight);
      const boxCol = Math.floor(j / boxWidth);
      const boxIndex = boxRow * boxesPerRow + boxCol;

      if (num === ".") continue;

      if (rows[i].has(num) || columns[j].has(num) || boxes[boxIndex].has(num)) {
        return false;
      }

      rows[i].add(num);
      columns[j].add(num);
      boxes[boxIndex].add(num);
    }
  }
  return true;
};