백준 30462 (C++) MEXchange

최초 업로드: 2025-11-30 06:31:35

최근 수정 시간: 2025-11-30 06:31:48

게시자: rlatjwls3333

카테고리: 백준

# [Gold I] MEXchange

[문제 링크](https://www.acmicpc.net/problem/30462)

## 문제 설명

길이가 $N$인 순열은 $1$부터 $N$까지의 정수가 정확히 한 번씩 등장하는 수열이다. 예를 들어, $\left[ 2,3,1,5,4 \right]$는 순열이지만 $\left[ 1,2,2 \right]$는 $2$가 두 번 등장하기 때문에 순열이 아니다. 또한 $\left[ 1,3,4 \right]$도 길이가 $3$이지만 $4$가 등장하기 때문에 순열이 아니다.

길이가 $N$인 순열 $A$가 주어졌을 때, 수열 $B$를 다음과 같이 정의하자.

$$B_i=\operatorname{MEX}\left( \{A_1,A_2,\cdots ,A_i\} \right)\ (1 \leq i \leq N)$$

길이가 $N$인 수열 $B$가 주어질 때, 순열 $A$를 구해보자.

$\operatorname{MEX}\left( S \right)$는 집합 $S$에 포함되지 않는 가장 작은 양의 정수이다. 예를 들어, $\operatorname{MEX}\left(\{ 1,2,5 \}\right) =3$이고 $\operatorname{MEX}\left(\{ 2,3,4 \}\right) =1$이다. 이 문제에서 정의한 $\operatorname{MEX}$는 그 값으로 $0$이 나올 수 없음에 주의하라.

## 입력

첫째 줄에 순열 $A$의 길이 $N$이 주어진다. $\left( 3\leq N\leq 200\, 000 \right)$

둘째 줄에 수열 $B$의 원소를 나타내는 $N$개의 정수 $B_i$가 공백으로 구분되어 주어진다. $\left( 1\leq B_i\leq N+1 \right)$

## 출력

첫째 줄에 $B$가 되는 순열 $A$가 존재하면 <code>Yes</code>를 출력하고 그렇지 않으면 <code>No</code>를 출력한다.

만약 존재한다면 둘째 줄에 순열 $A$의 원소를 공백으로 구분하여 출력한다. 답이 여러 가지라면 아무거나 출력한다.

## 풀이
순열 A가 존재하려면 순열 B가 오름차순으로 정렬되어 있어야 하고, B의 마지막 값이 N+1이어야 합니다.
1. B에 존재하는 유니크한 값을 뽑아내서 그 값보다 한 단계 큰 값의 첫 등장 위치에 할당합니다. (B[upper_bound(B, B+N, B[i])-B.begin()] = B[i])
2. 그 이후에는 남은 숫자들을 앞에서부터 오름차순으로 할당하면 됩니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

bool used[200'001];
int a[200'001], b[200'001];

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 for(int i=1;i<=n;i++) {
 cin >> b[i];
 if(i+1<b[i] || b[i-1]>b[i]) {
 cout << "No";
 return 0;
 }
 }
 if(b[n]!=n+1) {
 cout << "No";
 return 0;
 }

vector<int> v;
 for(int i=1;i<n;i++) {
 if(v.empty() || v.back()!=b[i]) v.push_back(b[i]);
 }
 int idx=0;
 for(int i=1;i<=n;i++) {
 if(idx<v.size() && v[idx]<b[i]) {
 used[v[idx]]=true;
 a[i]=v[idx++];
 }
 }

idx=1;
 cout << "Yes\n";
 for(int i=1;i<=n;i++) {
 if(!a[i]) {
 while(used[idx]) idx++;
 a[i]=idx++;
 }
 cout << a[i] << ' ';
 }
}
```