Valid Sudoku

ㅋㅋ·2022년 11월 23일
0

알고리즘-leetcode

목록 보기
55/135

9x9 크기의 "1~9"와 "." 문자가 담긴 2차원 벡터를 받는다. "."은 빈칸을 나타낸다.

해당 스도쿠 보드가 아래 3개의 조건을 만족하는지 체크하는 문제

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        static const int ITEM = 9;

        unordered_set<int> rowTable[ITEM]{};
        unordered_set<int> colTable[ITEM]{};
        unordered_set<int> subboxTable[ITEM]{};

        for (int y = 0; y < ITEM; y++)
        {
            for (int x = 0; x < ITEM; x++)
            {
                if (board[y][x] == '.')
                {
                    continue;
                }

                if (0 < rowTable[y].count(board[y][x]))
                {
                    return false;
                }

                if (0 < colTable[x].count(board[y][x]))
                {
                    return false;
                }

                int index = PositionToSubboxIndex(x, y);
                if (0 < subboxTable[index].count(board[y][x]) || index == -1)
                {
                    return false;
                }

                rowTable[y].insert(board[y][x]);
                colTable[x].insert(board[y][x]);
                subboxTable[index].insert(board[y][x]);
            }
        }

        return true;
    }

    int PositionToSubboxIndex(int x, int y)
    {
        switch (y)
        {
            case 0:
            case 1:
            case 2:
            if (x <= 2)
            {
                return 0;
            }
            else if (x <= 5)
            {
                return 1;
            }
            else 
            {
                return 2;
            }

            case 3:
            case 4:
            case 5:
            if (x <= 2)
            {
                return 3;
            }
            else if (x <= 5)
            {
                return 4;
            }
            else 
            {
                return 5;
            }

            case 6:
            case 7:
            case 8:
            if (x <= 2)
            {
                return 6;
            }
            else if (x <= 5)
            {
                return 7;
            }
            else 
            {
                return 8;
            }

            default:
            return -1;
        }
    }
};

0개의 댓글