[1364C] Ehab and Prefix MEXs

난이도: 1600

 

태그

• Constructive (구성적)
• Greedy (그리디)

 

풀이

1. 수 하나를 추가해서 mex의 결과값을 바꾸는 방법은?

\( \text{mex}(b_1, b_2, \ldots, b_{i-1}) = a_{i-1} \)에서

\( \text{mex}(b_1, b_2, \ldots, b_{i-1}, b_i) = a_i \)로 값이 바뀌려면 (즉, \( a_{i-1} \neq a_{i} \)라면),

\( b_i = a_{i-1} \)여야 합니다.

 

물론 값이 바뀐다고 정확히 \( a_i \)가 된다는 보장은 없지만,

\( b_i = a_{i-1} \)가 아니었다면 애초에 \( a_{i-1} = a_{i} \)가 되어버리기 때문에 위 경우로 고정시킬 수 있습니다.

 

2. 남은 칸을 채우는 방법은?

(1번)의 방법을 사용하면, \( a_{N} \)을 제외하고는 \( a \)에 있는 모든 수들을 \( b \)에서 등장시킬 수 있습니다.

어차피 \( a_{N} \)은 끝까지 등장하면 안 되니, 남은 건 \( a \)에 없는 수들을 적당히 사용하면 될 것 같네요.

 

\( a \)에서 등장하지 않는 어떤 수 \( \alpha \) \( (< a_{i}) \)를 생각해봅시다.

\( \alpha < a_{i} \)이므로, 이 수는 \( 1 \le j \le i \)인 어떤 \( j \)에서 등장해야만 합니다.

 

\( \alpha \)에 붙는 이외의 조건은 없고, \( a_{i} \)는 감소하지 않는 수열이므로,

이러한 수들을 그냥 빈 칸에 순서대로 넣는 걸 생각해볼 수 있습니다.

 

이렇게 하면 실제로 답이 나옵니다.

\( a_{i} \le i \)이고, 하나의 수를 2번 이상 사용하지 않으므로,

\( i \)개의 칸에 \( i \)개의 수를 적당히 적어낼 수 있기 때문입니다.

 

코드

저는 편의상 \( a_{N} \) 이상의 수들은 그냥 \( 10^6 \)으로 고정시켰습니다.

int arr[100020];
int chk[100020];
int ans[100020];
 
void Main(){
    int n; cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> arr[i]; chk[ arr[i] ] = i;
    }
    memset(ans, -1, sizeof(ans));
    int p = 1;
    for (int x = 0; x <= arr[n]; x++){
        if (chk[x] == 0){
            while (p <= n){
                if (ans[p] == -1){ break; }
                else{ p += 1; }
            }
            ans[p] = x;
        }
        else{
            ans[ chk[x]+1 ] = x;
        }
    }
    for (int i = 1; i <= n; i++){
        cout << (ans[i]==-1 ? 1000000 : ans[i]) << ' ';
    }
}