백준 13908 비밀번호

브루트 포스 문제이다.

근데 진짜 빼박 브루트 포스로 전체 탐색을 돈다...

n자리 수 공간을 탐색하면서 꼭 들어가야 하는 숫자가 없으면 출력하지 않고 들어간다면 가능성 있는 비밀번호이므로 출력한다.

비교는 단순하게 string으로 바꿔 각 자리수를 비교했다. 숫자가 커진다면 스트링으로 확인할때 메모리 문제나 속도에 문제가 있을 수 있을것 같다. 속도가 문제라면 숫자 변수형이 아닌, 다른 자료구조를 사용해(배열이라던가...) 숫자가 사용되는지 여부를 확인할 수 있을 것 같다.

하지만 이 문제는 7자리가 끝이다. 허허... 빡 탐색으로 구현했다.

---

#include <iostream>
#include <string>
#include <vector>

int main()
{
    int n, m, cnt = 0;
    std::vector<int> knowing;
    std::cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int tmp;
        std::cin >> tmp;
        knowing.push_back(tmp);
    }
    int max_len = 1;
    for (int i = 0; i < n; i++)
    {
        max_len *= 10;
    }
    for (int i = 0; i< max_len; i++)
    {
        std::string tmp = std::to_string(i);
        while (tmp.size() != n)
            tmp = "0" + tmp;
        
        bool available = true;
        for (int k : knowing)
        {
            bool test = false;
            for (char c : tmp)
            {
                if (c - '0' == k)
                    test = true;
            }
            if (!test)
            {
                available = false;
                break;
            }
        }
        if (available)
            cnt++;
    }
    std::cout << cnt;
    

}

 

발생 가능한 모든 비밀번호를 탐색한다. 최대 10^7 크기의 공간을 탐색하고, 거기서 각 자리마다 입력받은 숫자가 맞는지 확인하므로 10진수 10 * 최대 7자리이므로 7을 곱하면, 7*10^8 공간이다. 이정도면 전체 탐색할만한것 같다.

좀 급해서 쉬운것 잡아봤다. 같은 골드5여도 이건 좀 쉬운 편인것 같다. 좀 어려운걸 잡아봐야겠다.

 

오늘도 평온한 하루가 되길. 슨민.