[Leetcode] 36. Valid Sudoku - JS

https://leetcode.com/problems/valid-sudoku/description/?envType=study-plan-v2&envId=top-interview-150

 

 

 

 

1. 문제 분석

문제분석
--------------------
- 9 x 9 스도쿠가 유효한지 판단하라.
1. 각 열은 반복없는 1-9로 구성된다.
2. 각 행은 반복없는 1-9로 구성된다.
3. 각 3 x 3 부분 박스는 반복없는 1-9로 구성된다.

제한조건
--------------------
- board.length === 9
- board[i].length === 9
- board[i][j]는 1-9 또는 '.'이다.

 

2. 접근 방법

접근방법
--------------------
row, col 중첩 반복문을 통해 rows, cols 각 index에 set 자료구조 사용하여
'.'을 제외한 이미 등장했던 숫자가 등장하면 false 반환

3x3 box는 row와 col의 index에 따라 0~9번째 박스 인덱스를 지정해줄 수 있다.

boxIndex를 구하는 방법 설명
r = 0 일 때,
    - c = 0,1,2 이면 boxIndex = 0
    - c = 3,4,5 이면 boxIndex = 1
    - c = 6,7,8 이면 boxIndex = 2
r = 1 일 때,
    - c = 0,1,2 이면 boxIndex = 0
    - c = 3,4,5 이면 boxIndex = 1
    - c = 6,7,8 이면 boxIndex = 2
r = 2 일 때,
    - c = 0,1,2 이면 boxIndex = 0
    - c = 3,4,5 이면 boxIndex = 1
    - c = 6,7,8 이면 boxIndex = 2

r = 3 일 때,
    - c = 0,1,2 이면 boxIndex = 3
    - c = 3,4,5 이면 boxIndex = 4
    - c = 6,7,8 이면 boxIndex = 5

r = 4 일 때,
    - c = 0,1,2 이면 boxIndex = 3
    - c = 3,4,5 이면 boxIndex = 4
    - c = 6,7,8 이면 boxIndex = 5

그러므로...
boxIndex = Math.floor(r / 3) * 3 + Math.floor(c / 3);

rows, cols, boxes의 조건을 모두 통과하여 반복문이 종료되면 true를 반환

 

 

3. 코드

var isValidSudoku = function(board) {
    const rows = Array.from({length : 9}, () => new Set());
    const cols = Array.from({length : 9}, () => new Set());
    const boxes = Array.from({length : 9}, () => new Set());

    for (let r = 0; r < 9; r++) {
        for (let c = 0; c < 9; c++) {
            if (board[r][c] === '.') continue;

            let value = board[r][c];
            let boxIndex = Math.floor(r / 3) * 3 + Math.floor(c / 3); // ??

            if (rows[r].has(value) || cols[c].has(value) || boxes[boxIndex].has(value)) {
                return false;
            }

            rows[r].add(value);
            cols[c].add(value);
            boxes[boxIndex].add(value);
        }
    }
    return true;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(1)

- 공간복잡도: O(1)

 

9 x 9 스토쿠이므로 중첩 반복문을 사용하더라도 모수가 적기 때문에 시간 복잡도와 공간 복잡도가 상수값을 가질 수 있다.

3 x 3 박스의 조건을 체크할 때, boxIndex를 구하는 부분이 헷갈렸다.

아직 행렬에 익숙하지 않아서 그런 것 같으니 행렬 문제를 더 풀어봐야겠다.