C++ 학습/C++ 코딩인터뷰[5장]

[5. 배열] 5.17 스도쿠 체크

msugi 2025. 1. 22. 17:04

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include "Q5.h"
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec)
{
    os << "[";
    for (size_t i = 0; i < vec.size(); i++)
    {
        os << vec[i];
        if (i != vec.size() - 1)
        {
            os << ", ";
        }
    }
    os << "]";
    return os;
}
 
 cs
 
// main에서 vector 형태로 출력하기위한 기본 셋팅
 

 

Q 5.17 스도쿠 체크

9x9 크기의 미완성된 격자판이 2차원 배열로 주어졌을 때 이 게임의 해법이 존재하는지를 판별하자.

9개의 행, 9개의 열, 9개의 격자판에 비트배열을 사용해서 1~9까지의 숫자가 한번 이상 등장했는지를 테스트 하면된다.

해당 내용의 코드와 결과는 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 5.17 스도쿠 체크.cpp
#include<vector>
#include<deque>
 
bool HasDuplicate(const std::vector<std::vector<int>>& partial_assignment,
    int start_row, int end_row, int start_col, int end_col)
{
    std::deque<bool> is_present(size(partial_assignment) + 1, false);
    for (int i = start_row; i < end_row; i++)
    {
        for (int j = start_col; j < end_col; j++)
        {
            if (partial_assignment[i][j] != 0 &&
                is_present[partial_assignment[i][j]])
            { 
                return true;
            }
            is_present[partial_assignment[i][j]] = true;
        }
    }
    return false;
}
 
bool IsValidSudoku(const std::vector<std::vector<int>>& partial_assignment)
{
    for (int i = 0; i < size(partial_assignment); i++)
    {
        if (HasDuplicate(partial_assignment, i, i + 1, 0,
            size(partial_assignment)))
        { 
            return false; 
        }
    }
    for (int j = 0; j < size(partial_assignment); j++)
    {
        if (HasDuplicate(partial_assignment, 0,
            size(partial_assignment), j, j + 1))
        { 
            return false; 
        }
    }
    int region_size = sqrt(size(partial_assignment));
    for (int i = 0; i < region_size; i++)
    {
        for (int j = 0; j < region_size; j++)
        {
            if (HasDuplicate(partial_assignment, region_size * i,
                region_size * (i + 1), region_size * j, region_size * (j + 1)))
            { 
                return false;
            }
        }
    }
    return true;
}
 cs

시간복잡도는 O(3n2) 이다. (왜냐하면 행,렬,격자판 확인 n2 * 3)
추가적인 공간복잡도는 O(n)이다 (비트배열에 필요한 양)

 

1
2
3
4
// main.cpp
std::vector<std::vector<int>>TestVec16={{5,3,0,0,7,0,0,0,0},{6,0,0,1,9,5,0,0,0},
{0,9,8,0,0,0,0,6,0},{8,0,0,0,6,0,0,0,3},{4,0,0,8,0,3,0,0,1},{7,0,0,0,2,0,0,0,6},
{0,6,0,0,0,0,2,8,0},{0,0,0,4,1,9,0,0,5},{0,0,0,0,8,0,0,7,9}};
std::cout << "5-17 " << IsValidSudoku(TestVec16) << std::endl; //5-17
 cs

결과