백준 23820 (MEX) C++

문제

23820번: MEX

수열이 주어지면  수열 각각의 원소들의 곱집합에서 없는 숫자중 가장 작은 정수를 출력하면 됩니다.

예를들어 N이 3이고 수열이 {0, 1, 2} 라면 곱집합은 {0, 1, 2, 4} 가 됩니다. 여기서 없는 숫자중 가장 작은 정수는

3입니다.

N의 범위가 1부터 200만 이고 수열 a(i)의 범위 또한 0부터 200만 입니다.

단순히 모든 수열을 순회하면서 확인하면 O(N^2) 이 이므로 최악의 경우 

2000000 *2000000 = 40000000000(백억)의 시간복잡도가 나와서 시간초과가 나게 됩니다.

Brute force방법 밖에 생각이 나지 않아 답이 될 수 없는 경우의 수를 제외 시키기로 했습니다.

 

1) 먼저 수열 a(i) 에 0이 없다면 답은 바로 0이됩니다. 마찬가지로 a(i)에 1이 없다면 바로 1이 됩니다.

2) 답은 무조건 2000000이상의 소수중 가장 작은 소수(2000003) 보다 작습니다.

   왜냐하면 1 ≤ a(i) ≤ 2000000 중에서 a(i) * a(j) 는 항상 합성수 입니다. 

   따라서 집합 S에는 항상 합성수만 들어가게 됩니다. 

   그래서 미리 a(i) * a(j)가 2000003을 넘어가면 무시하고 다음으로 넘어가게 됩니다.

 

---

전체코드 입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll arr[3000000];
bool check[3000000];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    ll n;
    cin >> n;
    for (ll i = 0, a; i < n; i++) {
        cin >> a;
        arr[a]++;
    }
    for (int i = 0; i <= 1; i++) {
        if (!arr[i]) {
            cout << i;
            return 0;
        }
    }
    for (ll i = 1; i <= 2000000; i++) {
        if (!arr[i])continue;
        for (ll j = 1; j <= 2000000; j++) {
            if (i * j > 2000003)break;
            if (!arr[j])continue;
            check[i * j] = true;
        }
    }
    for (int i = 2; i <= 2000003; i++) {
        if (check[i])continue;
        cout << i;
        return 0;
    }
 
  
 
    return 0;
}