백준 9011 순서 :: 들짐승

<링크>

https://www.acmicpc.net/problem/9011

<풀이>

내앞에 나보다 작은 수가 몇 개 있는지 주어지면 원래 수열을 찾는다.
맨 뒤부터 참조하면 된다.
맨 뒤에서 9라면 나는 10일 수 밖에 없다.
10
0 0 0 2 0 1 6 7 6 9 

맨뒤부터 숫자 그대로를 index로 사용하고 벡터에서 erase()하였다.
벡터에서 특정 위치의 원소를 erase하면 뒤에 있는 것들이 앞으로 한칸씩 땡겨오기 때문에 사용했다.
v : 1 2 3 4 5 6 7 8 9 10
v[9]=10 ->제거
1 2 3 4 5 6 7 8 9
v[6]=7 ->제거
1 2 3 4 5 6 8 9
v[7]=9 ->제거
1 2 3 4 5 6 8
v[6]=8 -> 제거
1 2 3 4 5 6
...
v[0]=6 ->제거

제거한값들을 거꾸로 나열하면 답이 된다.

IMPOSSIBLE이 뜨는 경우는 잘 모르겠어서 그냥 마지막 예제 입력을 위 과정대로 해봤더니
잘못된 입력이 있으면 접근하고자 하는 index가 현재 남아있는 벡터의 범위를 벗어나게 된다.
그냥 예제 따라해보면 쉽게 풀 수 있다.

<소스코드>

#include<stdio.h>
#include<vector>
using namespace std;
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int N;
        scanf("%d", &N);
        vector<int> v;
        for (int i = 1; i <= N; ++i)
            v.push_back(i);
        int seq[101];
        int res[101];
        for (int i = 0; i < N; ++i)
            scanf("%d", seq + i);
        int check=1;
        for (int i = N - 1; i >= 0; --i)
        {
            int to = seq[i];
            if (to >= v.size())
            {
                printf("IMPOSSIBLE");
                check = 0;
                break;
            }
            res[i] = v[to];
            v.erase(v.begin() + to);
        }
        if (check)
            for (int i = 0; i < N; ++i)
                printf("%d ", res[i]);
        printf("\n");
 
 
    }
}