백준 1898 - 이전 수열은 어떤 수열일까

이전 수열은 어떤 수열일까

풀이

원래 수가 x이고 새로운 수가 nx로 두고 싶다고 하자.
왼쪽부터 접근한다고 했을 때 가장 작은 수가 되려면 nx는 x보다 작으면 좋고 최소한 같아야 한다.
따라서 nx = x-1이거나 x이다. nx = x인 경우는 그냥 그대로 넣으면 되므로 상관없고 nx = x-1인 경우를 살펴보자.

원래:   x    ...  x-1  
새로운: x-1  ...   ?  

? 자리에 x-1은 이미 사용해서 올 수 없으므로 x-2나 x가 가능하다. 만약 ?에 x-2가 오게 된다면 원래의 x-2에는 x-3, x-2, x-1중에서 쓸 수 있는 수가 x-3만 사용 가능하므로 점점 작아진다. 이는 1이상의 차이가 나는 자리가 생길 수 밖에 없다.
따라서 ?는 x만 올 수 있다.

이를 이용해서 그리디하게 풀면 해결 가능하다.

코드

#include <bits/stdc++.h>

#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For(i, a, b) for(ll i=(a); i<(b); i++)
#define FOR(i, a, b) for(ll i=(a); i<=(b); i++)
#define Bor(i, a, b) for(ll i=(a); i>(b); i--)
#define BOR(i, a, b) for(ll i=(a); i>=(b); i--)
#define ft first
#define sd second

using namespace std;
using ll = long long;
using lll = __int128_t;
using ulll = __uint128_t;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int INF = 987654321;
const int INF0 = numeric_limits<int>::max();
const ll LNF = 987654321987654321;
const ll LNF0 = numeric_limits<ll>::max();

void solve() {
    int n; cin >> n;
    vector<int> link(n+1,-1);
    FOR(i,1,n) {
        int x; cin >> x;
        if(link[x] == -1) {
            for(int nx=max(1,x-1); nx<=min(n,x+1); nx++) {
                if(link[nx] != -1) continue;
                link[x] = nx;
                link[nx] = x;
                break;
            }
        }
        cout << link[x] << endl;
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int TC=1;
//    cin >> TC;
    FOR(tc, 1, TC) {
//        cout << "Case #" << tc << ": ";
        solve();
    }


    return 0;
}