BOJ 1898 - 이전 수열은 어떤 수열일까

BOJ 1898 - 이전 수열은 어떤 수열일까

항상 swap 연산만으로 해를 구성할 수 있다.

$i<j$ 이고 $j$가 $a[i] - 1$ 가 있는 인덱스라고 하자.

그럼 $i , j$를 스왑해주면 된다.

그럼 이제 $j$도 쓸모없어진다. $j$는 $a[i] - 1$ 이였는데 $a[i]$ 가 되어버렸고, $a[i-1]$ 은 $i$ 가 되어서 앞에있기 때문에 아무것도 안교체하는게 이득이 되버린다.

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;
}