수열의 MEX(minimal excluded)¶

크기가 $N$인 배열 $A$가 주어집니다. 배열에 없는 음이 아닌 원소 중 가장 작은 것을 찾아야 합니다. 이 수를 흔히 MEX(minimal excluded)라고 부릅니다.

$$ \begin{align} \text{mex}(\{0, 1, 2, 4, 5\}) &= 3 \\ \text{mex}(\{0, 1, 2, 3, 4\}) &= 5 \\ \text{mex}(\{1, 2, 3, 4, 5\}) &= 0 \\ \end{align} $$

크기가 $N$인 배열의 MEX는 결코 $N$보다 클 수 없다는 점에 주목하십시오.

가장 쉬운 방법은 배열 $A$의 모든 원소로 집합을 만들어서 어떤 수가 배열에 속하는지를 빠르게 확인할 수 있게 하는 것입니다. 그런 다음 $0$부터 $N$까지 모든 수를 차례로 확인하면서 현재 수가 집합에 없으면 그 수를 반환하면 됩니다.

구현¶

다음 알고리즘은 $O(N \log N)$ 시간에 동작합니다.

int mex(vector<int> const& A) {
    set<int> b(A.begin(), A.end());

    int result = 0;
    while (b.count(result))
        ++result;
    return result;
}

알고리즘에서 MEX를 $O(N)$에 계산해야 한다면 집합 대신 불리언 벡터를 사용하면 됩니다. 이때 배열의 크기는 가능한 최대 배열 크기 이상이어야 한다는 점에 주목하십시오.

int mex(vector<int> const& A) {
    static bool used[MAX_N+1] = { 0 };

    // mark the given numbers
    for (int x : A) {
        if (x <= MAX_N)
            used[x] = true;
    }

    // find the mex
    int result = 0;
    while (used[result])
        ++result;

    // clear the array again
    for (int x : A) {
        if (x <= MAX_N)
            used[x] = false;
    }

    return result;
}

이 방법은 빠르지만 MEX를 한 번만 계산하면 되는 경우에만 잘 동작합니다. 예를 들어 배열이 계속 바뀌어서 MEX를 반복해서 계산해야 한다면 이 방법은 효율적이지 않습니다. 그런 경우에는 더 나은 방법이 필요합니다.

배열 갱신이 있는 경우의 MEX¶

이 문제에서는 배열의 수를 하나씩 변경하고, 갱신할 때마다 배열의 새로운 MEX를 계산해야 합니다.

이러한 쿼리를 효율적으로 처리하려면 더 나은 자료 구조가 필요합니다.

한 가지 방법은 $0$부터 $N$까지 각 수의 빈도를 구하고 그 위에 트리 형태의 자료 구조를 만드는 것입니다. 예를 들어 세그먼트 트리나 트립(treap)을 사용할 수 있습니다. 각 노드는 수의 구간 하나를 나타내며, 그 구간의 전체 빈도와 함께 구간에 있는 서로 다른 수의 개수도 저장합니다. MEX에 대한 이진 탐색을 수행하면 이 자료 구조를 $O(\log N)$ 시간에 갱신할 수 있으며, MEX도 $O(\log N)$ 시간에 찾을 수 있습니다. 구간 $[0, \lfloor N/2 \rfloor)$를 나타내는 노드에 서로 다른 수가 $\lfloor N/2 \rfloor$개 들어 있지 않다면 그중 하나가 빠져 있는 것이므로 MEX는 $\lfloor N/2 \rfloor$보다 작습니다. 따라서 트리의 왼쪽 가지로 재귀하면 됩니다. 그렇지 않으면 MEX는 $\lfloor N/2 \rfloor$ 이상이므로 트리의 오른쪽 가지로 재귀하면 됩니다.

표준 라이브러리 자료 구조인 map과 set을 사용할 수도 있습니다(여기에서 설명한 방법에 기반합니다). map으로는 각 수의 빈도를 기록하고, set으로는 현재 배열에 없는 수들을 나타냅니다. set은 정렬되어 있으므로 *set.begin()이 MEX가 됩니다. 전체적으로 $O(N \log N)$의 전처리가 필요하며, 그 뒤에는 MEX를 $O(1)$에 계산하고 갱신을 $O(\log N)$에 수행할 수 있습니다.

class Mex {
private:
    map<int, int> frequency;
    set<int> missing_numbers;
    vector<int> A;

public:
    Mex(vector<int> const& A) : A(A) {
        for (int i = 0; i <= A.size(); i++)
            missing_numbers.insert(i);

        for (int x : A) {
            ++frequency[x];
            missing_numbers.erase(x);
        }
    }

    int mex() {
        return *missing_numbers.begin();
    }

    void update(int idx, int new_value) {
        if (--frequency[A[idx]] == 0)
            missing_numbers.insert(A[idx]);
        A[idx] = new_value;
        ++frequency[new_value];
        missing_numbers.erase(new_value);
    }
};

수열의 MEX(minimal excluded)¶

구현¶

배열 갱신이 있는 경우의 MEX¶

연습 문제¶