3809. 화섭이의 정수 나열

3809. 화섭이의 정수 나열

나는 그냥 N이 1000개가 최대이기 때문에,

1000의 자리 수 이전에서 최소값이 무조건 발생한다고 생각했다.

즉, N=1000 이 되어 숫자가 1000개가 있을 때 숫자가 1000개가 생길 것이다. 그렇다고 할때

수가 1개인 예를 들어 0,1,2,3,4~,9 는 1000개가 나오게 된다.

수가 2개인 예를 들어 10,11,..,99 는 999개가 나오게 된다.

수가 3개인 100,101,...999 는 998개가 나오게 된다.

수가 4개인 1000,1001,...9999는 997개가 나오게 된다. 

즉 수가 4개인 값들은 997개가 나와도 절대 1000~9999를 다 나타낼 수 없기 때문에 최소값이 무조건 발생하게 된다.

나는 이점을 이용해서 main 에서 for문을 4까지 돌렸다.

그리고 0일 때는 1자리, 1일때는 2자리를 구하는 방식으로 string 을 사용해서 문제를 풀었다.

<정답 코드>

#include<iostream>
#include<vector>
#include<string>
#include<math.h>
using namespace std;
bool used[10001];
vector<char> v;
int n;
void init()
{
    v.assign(n,0);
 
    for (int i = 0; i < 1001; i++)
    {
        used[i] = false;
    }
}
int check(int k)
{
 
    for (int i = 0; i < pow(10, k);i++)
    {
        if (!used[i])
        {
            return i;
        }
    }
 
 
    return -1;
 
}
void go(int k)
{
    for (int i = 0; i+k < n; i++)
    {
        string s = "";
        s += v[i];
 
        for (int j = 1; j <= k; j++)
        {
            s += v[j + i];
        }
 
        used[stoi(s)] = true;
    }
 
 
 
 
}
int main()
{
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        cin >> n;
        init();
        for (int i = 0; i < n; i++)
        {
            cin >> v[i];
        }
 
        for (int i = 0; i < 4; i++)
        {
            go(i);
            int k = check(i);
            if (k != -1)
            {
                cout << "#" << t << " " << k << "\n";
                break;
            }
        }
 
 
    }
    
 
    return 0;
}