[NeetCode-LeetCode] Valid Sudoku JAVA

반응형

728x90

[NeetCode-LeetCode] Valid Sudoku - Medium

---

접근

• 브루트 포스

---

풀이

Grind75에 있던 문제를 다 풀고 NeetCode로 넘어왔다. NeetCode에서 겹치치 않는 안 풀었던 문제를 위주로 풀어볼 예정이다. 첫 번째 문제로 스도쿠를 검증하는 문제이다. 말 그대로 주어진 스도쿠 판이 스도쿠 규칙을 만족하고 있는지 검사하는 문제이다. 처음 문제를 봤을 때 주어진 스도쿠 판으로 스도쿠를 완성할 수 있는지를 검사하는 문제인 줄 알고 그냥도 완성하기 힘든 스도쿠를 완성할 수 있는지 검사하라니 Medium 난이도가 맞는가 싶어 요구하는 시간 복잡도를 봤더니 n의 제곱이었다. n의 제곱이라는 뜻은 주어진 스도쿠 2차원 배열을 한 번만 방문해서 완성하라는 의미인데 그게 가능한가 싶어 생각해 보니 현재 주어진 스도쿠 판이 모두 스도쿠 규칙을 만족하는지만 검사해 보면 되는 것이었다.

    public boolean isValidSudoku(char[][] board) {
	HashSet<Integer>[] rows = new HashSet[9];
        HashSet<Integer>[] cols = new HashSet[9];
        HashSet<Integer>[] subgrids = new HashSet[9];

        for (int i = 0; i < 9; i++) {
            rows[i] = new HashSet<>();
            cols[i] = new HashSet<>();
            subgrids[i] = new HashSet<>();
        }

 스도쿠는 해당 숫자가 존재하는 열, 행, 같은 사각형 내부엔 1부터 9까지 숫자가 1개씩만 존재할 수 있다. 문제에서 힌트로 Set을 사용해 숫자를 체크하라 되어있어 Set을 사용해 봤다. 스도쿠 판은 9 x 9 사이즈로 9개의 행, 열과 3 x 3 사각형이 9개 존재한다. 각 종류별로 체크를 위해 각각 9개씩 개별적인 Set을 통해 체크하게 된다.

	for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char num = board[i][j];

                if (num == '.') continue; 

                int rowKey = num;
                int colKey = num;
                int subgridKey = num;

                int subgridIndex = (i / 3) * 3 + (j / 3);

                if (rows[i].contains(rowKey) || cols[j].contains(colKey) || subgrids[subgridIndex].contains(subgridKey)) {
                    return false; 
                }
                
                rows[i].add(rowKey);
                cols[j].add(colKey);
                subgrids[subgridIndex].add(subgridKey);
            }
        }

        return true; 
    }

스도쿠 판을 검증하는 과정이다. 해당 칸이 숫자가 없다면 넘어가고 숫자가 존재한다면 인덱스 계산을 통해 현재 칸이 속한 행, 열, 사각형의 Set에서 이미 같은 숫자가 존재하는지 체크한다. 숫자가 존재하지 않는다면 현재 숫자를 추가하고 다음으로 넘어가고 숫자가 이미 존재한다면 스도쿠 규칙을 만족하지 못하기 때문에 false를 반환한다.

Set

---

배열

힌트에선 Set을 사용하라 했지만 당연하게 배열로 대체할 수 있다. Set 배열 대신 2차원 배열을 사용해 각 숫자에 해당하는 인덱스의 값을 비교해 체크를 하면 된다.

    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][10];
        int[][] cols = new int[9][10];
        int[][] subgrids = new int[9][10];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char num = board[i][j];

                if (num == '.')
                    continue;

                int digit = num - '0';

                int subgridIndex = (i / 3) * 3 + (j / 3);

                if (rows[i][digit] != 0 || cols[j][digit] != 0 || subgrids[subgridIndex][digit] != 0) {
                    return false;
                }

                rows[i][digit] = 1;
                cols[j][digit] = 1;
                subgrids[subgridIndex][digit] = 1;
            }
        }

        return true;
    }

각 숫자인 1~9를 편하게 매핑하기 위해서 배열의 크기를 10으로 선언했고 해당 숫자의 인덱스 값이 1이라면 이미 숫자가 존재한다는 뜻으로 false를 반환하면 된다. Set대신 배열을 사용하기 때문에 더 빠르게 접근이 가능하다.

2차원 배열

---

전체 코드

Set

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashSet<Integer>[] rows = new HashSet[9];
        HashSet<Integer>[] cols = new HashSet[9];
        HashSet<Integer>[] subgrids = new HashSet[9];

        for (int i = 0; i < 9; i++) {
            rows[i] = new HashSet<>();
            cols[i] = new HashSet<>();
            subgrids[i] = new HashSet<>();
        }

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char num = board[i][j];

                if (num == '.') continue; 

                int rowKey = num;
                int colKey = num;
                int subgridKey = num;

                int subgridIndex = (i / 3) * 3 + (j / 3);

                if (rows[i].contains(rowKey) || cols[j].contains(colKey) || subgrids[subgridIndex].contains(subgridKey)) {
                    return false; 
                }
                
                rows[i].add(rowKey);
                cols[j].add(colKey);
                subgrids[subgridIndex].add(subgridKey);
            }
        }

        return true; 
    }
}

 

배열

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][10];  
        int[][] cols = new int[9][10];  
        int[][] subgrids = new int[9][10];   

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char num = board[i][j];

            if (num == '.') continue; 

            int digit = num - '0';  

            int subgridIndex = (i / 3) * 3 + (j / 3);  

            if (rows[i][digit] != 0 || cols[j][digit] != 0 || subgrids[subgridIndex][digit] != 0) {
                return false; 
            }

            rows[i][digit] = 1;
            cols[j][digit] = 1;
            subgrids[subgridIndex][digit] = 1;
        }
    }

    return true; 
}
}