LeetCode: 36번 (Valid Sudoku) [JAVA]

문제 링크

https://leetcode.com/problems/valid-sudoku/

Valid Sudoku - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 행, 열, 지정된 구역 별로 각각의 HashSet 배열들을 초기화
2. 주어진 9x9 char 배열을 돌며 숫자인 경우 맞는 행, 열, 구역 HashSet에서 중복이 존재하는 지 탐색
3. 탐색 결과 중복이 존재하면 해당 반복문을 탈출 후 false를 반환, 중복이 없다면 탐색한 3개의 HashSet에 값을 삽입
4. 모든 구역에 중복이 없음이 확인되면, true를 반환

 문제에서 요구하는 부분이 단순히 주어진 board 배열 속 숫자들에 대해서만 스도쿠의 조건에 맞는 지 확인하는 것이기 때문에, HashSet을 활용해 중복을 체크하면 된다. 행, 열, 지정된 구역 별로 각각의 HashSet 배열들을 초기화한 후, board 배열을 돌며 숫자가 주어진 경우에 탐색을 진행한다. 해당 위치에 맞는 행, 열, 구역 HashSet에서 중복을 탐색한 후, 만약 중복이 존재하면 그대로 false를 반환한다. 모든 반복문을 돌고나서도 중복이 확인되지 않는다면, 맞는 스도쿠 퍼즐이기에 true를 반환하면 된다.

 

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashSet<Integer>[] rowSets = new HashSet[9], colSets = new HashSet[9];
        HashSet<Integer>[][] boxSets = new HashSet[3][3];

        for (int i = 0; i < 9; i++) {//HashSet 초기화
            rowSets[i] = new HashSet<>();
            colSets[i] = new HashSet<>();
            boxSets[i / 3][i % 3] = new HashSet<>();
        }

        for (int i = 0; i < 9; i++) {//이차원 board 배열 탐색
            for (int j = 0; j < 9; j++) {
                if (board[i][j]!='.') {
                    int num = board[i][j];

                    if (!rowSets[i].contains(num) && !colSets[j].contains(num) && !boxSets[i / 3][j / 3].contains(num)) {
                        rowSets[i].add(num);
                        colSets[j].add(num);
                        boxSets[i / 3][j / 3].add(num);
                    } else {//중복이 발견된 경우
                        return false;
                    }
                }
            }
        }

        return true;
    }
}

결과