BOJ 1898 - 이전 수열은 어떤 수열일까
항상 swap 연산만으로 해를 구성할 수 있다.
이고 가 가 있는 인덱스라고 하자.
그럼 를 스왑해주면 된다.
그럼 이제 도 쓸모없어진다. 는 이였는데 가 되어버렸고, 은 가 되어서 앞에있기 때문에 아무것도 안교체하는게 이득이 되버린다.
void solve() {
int n;
cin >> n;
vi a(n + 1), b(n + 1, -1);
fv1(a);
b = a;
vi used(n + 1), idx(n + 1);
for (int i = 1; i <= n; i++) idx[a[i]] = i;
for (int i = 1; i <= n; i++) {
if (used[a[i]] || a[i] == 1) continue;
if (used[a[i] - 1]) continue;
int j = idx[a[i] - 1];
if (j < i) continue;
swap(b[i], b[j]);
used[a[i]] = used[a[i] - 1] = 1;
}
for (int i = 1; i <= n; i++) cout << b[i] << endl;
}
Comments