리트코드 - 36. Valid Sudoku

리트코드 - 36. Valid Sudoku

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

 

문제 설명

9x9 스도쿠 보드가 유효한지 확인하세요. 채워진 셀만 다음 규칙에 따라 유효성을 검증할 필요가 있습니다:

• 각 행은 반복 없이 숫자 1-9를 포함해야 합니다.
• 각 열은 반복 없이 숫자 1-9를 포함해야 합니다.
• 그리드의 아홉 개 3x3 서브-박스 각각은 반복 없이 숫자 1-9를 포함해야 합니다.

참고:

• 스도쿠 보드(부분적으로 채워짐)는 유효할 수 있지만 반드시 풀 수 있는 것은 아닙니다.
• 언급된 규칙에 따라 채워진 셀만 유효성을 검증할 필요가 있습니다.

 

풀이코드

class Solution {
    public boolean isValidSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            if (!isRowValid(board, i) || !isColumnValid(board, i) || !isSquareValid(board, i)) {
                return false;
            }
        }
        return true;
    }

    private boolean isRowValid(char[][] board, int row) {
        Set<Character> set = new HashSet<>();
        for (int j = 0; j < 9; j++) {
            if (!isValid(set, board[row][j])) {
            	return false;
            }
        }
        return true;
    }

    private boolean isColumnValid(char[][] board, int column) {
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < 9; i++) {
            if (!isValid(set, board[i][column])) {
            	return false;
            }
        return true;
    }

    private boolean isSquareValid(char[][] board, int square) {
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < 9; i++) {
            int row = 3 * (square / 3) + i / 3;
            int column = 3 * (square % 3) + i % 3;
            if (!isValid(set, board[row][column])) {
                return false;
            }
        }
        return true;
    }

    private boolean isValid(Set<Character> set, char num) {
        if (num == '.') {
            return true;   
        }
        if (set.contains(num)) {
            return false;
        }
        set.add(num);
        return true;
    }
}

코드설명

스도쿠 배열이 주어지면 유효한 스도쿠인지 확인하는 문제이다.

문제의 조건에서 가로, 세로, 그리고 각 사각형에서 중복된 숫자가 있지 않으면 유효한 스도쿠이므로 이것만 확인해주면 된다.

 

Set 자료구조는 중복을 허용하지 않으므로 가로,세로, 사각형을 순회할 때 set에 값을 넣으며 중복을 확인해주면 된다.

contains 메소드를 이용하여 값을 확인하여 이미 있는 경우 false를 리턴하면 된다.

 

먼저, isRowValid 메소드에서는 행에서 중복을 확인한다.

가로를 순회하며 char 값이 '.' 이거나 set에 들어있지 않은 값이면 set에 추가후 true를 리턴한다.

만약 set에서 중복이 발견하면 false를 리턴하고, 또 이를 상위 메소드로 전달한다.

문제에서 '.' 값은 빈값을 의미하며 중복이어도 되는 값이므로 맨처음 set 값을 확인해버리면 의도하지 않은 결과가 나온다.

따라서

'.' 값이라면 -> true 리턴

set 중복이 있으면 -> false 리턴

set에 추가 후 true 리턴

의 순서를 따랐다.

 

isColumValid도 완전히 동일한 원리로 진행된다.

 

문제에서 가장 핵심은 사각형을 어떻게 순회하는가? 이다. (isSquareValid 메소드)

총 9번 순회를 하고, 그 9번에서 각각 움직여주면 되는데 dp배열을 변형하여 움직임을 지정해줘도 되지만 규칙적인 것을 활용하였다.

먼저 가로가 움직이는 동안 가로는 0으로 고정, 세로의 인덱스는 0~2 이동한다.

다음으로 두번째 줄을 움직이는 1일 때도 세로의 인덱스는 0~2, 마찬가지로 2일 때도 0~2 이다.

0부터 8까지 i인덱스가 이동할 때 i / 3 를 해주면 가로는 해결되고, 세로는 i % 3을 해주면 해결된다.

 

이제 다음 사각형을 순회해야 하는데 이것 좌표를 구해보면 규칙을 따르고 있다.

[0,0] [0,3] [0,6]

[3,0] [3,3] [3,6]

[6,0] [6,3] [6,6]

 

0부터 9까지 순회하며 가로와 세로 모두 0, 3, 6을 반복한다.

가로는 3 * (square / 3) 을 하면 괄호 안을 먼저 계산하여 int형으로 바꾸는 과정에서 정수로 바뀌므로 원하는 인덱스를 얻을 수 있고,

세로는 3 * (square % 3)을 하면 역시 원하는 인덱스를 얻을 수 있다.

 

따라서 이 둘을 합치면

int row = 3 * (square / 3) + i / 3;
int column = 3 * (square % 3) + i % 3;

이런 공식을 얻을 수 있다.

 

이렇게 하여 순회하면 유효한 스도쿠인지 확인이 가능하다.

가로, 세로, 사각형을 논리적으로 하나씩 확인하는 것이 중요한 문제라고 생각된다.

 

시간복잡도 - O(1)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

초기코드

class Solution {
    public boolean isValidSudoku(char[][] board) {
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < 9; i++) {
            set = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                char num = board[i][j];
                if (num != '.' && set.contains(num)) {
                    return false;
                }
                set.add(num);
            }
        }

        for (int i = 0; i < 9; i++) {
            set = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                char num = board[j][i];
                if (num != '.' && set.contains(num)) {
                    return false;
                }
                set.add(num);
            }
        }

        for (int square = 0; square < 9; square++) {
            set = new HashSet<>();
            for (int i = 0; i < 9; i++) {
                int rowIdx = 3 * (square / 3) + i / 3; 
                int colIdx = 3 * (square % 3) + i % 3;
                char num = board[rowIdx][colIdx];
                if (num != '.' && set.contains(num)) {
                    return false;
                }
                set.add(num);
            }
        }
        return true;
    }
}

 

일단 구현을 빡하고 나서 리팩토링을 거쳐 구현코드로 만들었다.

처음부터 너무 완벽하게 하려는 마음을 버리면 생각보다 빨리 풀릴수 있는 것 같다.

 

정리

스도쿠를 순회하는 방법