LeetCode 36 - Valid Sudoku

Valid Sudoku - LeetCode

9x9 크기의 스도쿠 판이 유효할 수 있는지 판단하라.

빈칸은 다음과 같은 규칙으로 채워진다.

1. 각각 row는 중복 없는 1~9 사이 숫자로 이루어진다.
2. 각 col은 중복 없는 1~9 사이 숫자로 이루어진다.
3. 3x3의 9개의 서브박스는 중복 없는 1~9 사이 숫자로 이루어진다.

숫자를 채워 넣는 스도쿠가 아니라 그냥 현재 스도쿠의 상태를 판정하는 문제이다. 중복 확인만 잘하면 된다.

중복 확인은 어떻게 해야할까? 열과 행은 각각을 HashSet으로 관리하면 될 것 같다.

박스의 경우 어떻게 해야할까? 박스의 대표 인덱스를 하나 표현할 수 있으면 좋을 것 같다.

이거는 (r / 3) * 3 + (c / 3) 이면 각 박스에 속하는 값들이 모두 같은 결과를 내게 된다. 따라서 해당 결괏값을 id로 사용하겠다.

class Solution {
    public boolean isValidSudoku(char[][] board) {
        Map<Integer, Set<Character>> rowMap = new HashMap<>();
        Map<Integer, Set<Character>> colMap = new HashMap<>();
        Map<Integer, Set<Character>> boxMap = new HashMap<>();

        for (int i = 0; i < 9; i++) {
            rowMap.put(i, new HashSet<>());
            colMap.put(i, new HashSet<>());
            boxMap.put(i, new HashSet<>());
        }

        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] != '.') {
                    char value = board[r][c];
                    if (rowMap.get(r).contains(value)) return false;
                    if (colMap.get(c).contains(value)) return false;
                    int boxId = (r / 3) * 3 + (c / 3);
                    if (boxMap.get(boxId).contains(value)) return false;

                    rowMap.get(r).add(value);
                    colMap.get(c).add(value);
                    boxMap.get(boxId).add(value);
                }
            }
        }

        return true;
    }
}