Valid Sudoku

💬 문제

[문제 링크]

2차원 배열로 주어지는 스도쿠 문제 board
행, 열, 3*3 박스에 1~9가 겹치지 않고 들어있는지 확인
유효한 상태면 true 아니면 false 반환
비어있는 칸은 '.'으로, 숫자는 1~9만 들어있음

✍️ 나의 풀이

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
    let row = new Set();
    let col = new Set();
    let box = new Set();

    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (board[i][j] === '.')
                continue ;
            else if (row.has(`${i} ${board[i][j]}`) || 
                     col.has(`${j} ${board[i][j]}`) || 
                     box.has(`${Math.floor(i / 3) * 3 + Math.floor(j / 3)} ${board[i][j]}`))
                return false;
            row.add(`${i} ${board[i][j]}`);
            col.add(`${j} ${board[i][j]}`);
            box.add(`${Math.floor(i / 3) * 3 + Math.floor(j / 3)} ${board[i][j]}`);
        }
    }

    return true;
};

행, 열, 3*3 박스의 숫자 겹침을 체크하기 위한 set을 각각 생성
board를 2중 for문으로 한칸씩 돌면서 숫자를 만나면
해당 숫자가 각각의 set에 들어있는지 확인
있으면 바로 중복이므로 false 반환
없으면 set에 추가한 후 다음칸 확인
각 행, 열, 박스를 구분하기 위해 저장할 때는 문자열로 '번호 숫자' 식으로 저장

📌 결과

Accepted
Runtime 60ms (Beats 86.25%)
Memory 52.50MB (Beats 55.60%)

📚 러닝 포인트

알고리즘 자체는 어렵지 않았는데 자료구조를 어떤 것을 활용해야 하나 조금 고민했던 것 같다. sliding window 문제들을 풀기 이전에 map을 사용해보지 않았던 것처럼 set도 잘 안써봤어서 그런지 바로 떠오르지가 않았다. 중복이 없는 것을 확인해야 한다 = set 활용을 잘 기억하고, 또 다양한 오브젝트를 적재적소에 사용할 수 있도록 많이 써봐야할 것 같다. 그리고 부끄럽지만 알고리즘 면에서는 box 구분하는 방법(계산식)이 바로 떠오르지 않아서 적으면서 찾아냈다... 마지막으로 메모리를 조금 줄여볼까 해서 set을 하나로 통합해봤는데 딱히 달라지지 않았고, board[i][j]로 참조하는 부분을 하나의 변수에 담아서 대체해봤더니 아주 조금 줄어들었다.