[알고리즘] Inversion Sequence

문제 설명

• 1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 Inversion Sequence라 한다.
• 예를 들어 다음과 같은 수열의 경우
  • 4 8 6 2 5 1 3 7
  • 1앞에 놓인 1보다 큰 수는 4, 8, 6, 2, 5. 이렇게 5개이고, 2앞에 놓인 2보다 큰 수는 4, 8, 6. 이렇게 3개,
  • 3 앞에 놓인 3보다 큰 수는 4, 8, 6, 5 이렇게 4개……
  • 따라서 4 8 6 2 5 1 3 7 의 inversion sequence 는 5 3 4 0 2 1 1 0 이 된다.
• n과 1부터 n까지의 수를 사용하여 이루어진 수열의 inversion sequence가 주어졌을 때, 원래 의 수열을 출력하는 프로그램을 작성하세요.

구현 방식

• 가장 큰 숫자 부터 하나씩 삽입정렬 시킨다.
• 예를 들어서 문제와 같은 inversion sequence 인 5 3 4 0 2 1 1 0 가 있다면
• 8 은 앞에 아무것도 없으므로 삽입정렬 시키면 [8] 이고,
• 7 은 7 앞에 큰 숫자가 한개 와야하므로 [8 , 7]에 위치한다.
• 6 은 6 앞에 큰 숫자가 한개 와야하므로 7을 한칸 미루고 [8 , 6, 7] 로 배치한다.
• 5 는 5 앞에 큰 숫자가 두개 와야하므로 7을 한칸 미루고 [8, 6, 5, 7] 로 배치한다.
• 4 는 4 앞에 큰 숫자가 없어야 하므로 [8, 6, 5, 7]을 한칸 씩 미루고 [4, 8, 6, 5, 7] 로 배치한다.
• 이런식으로 쭉쭉 짜면 된다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;


void solution(int N, vector<int> inputs);


int main()
{
    int N;
    cin >>  N;
    vector<int> inputs = vector<int>(N);
    for (int i = 0; i < N; i++)
    {
        cin >> inputs[i];
    }

    solution( N, inputs);

}

void solution(int N, vector<int> inputs) {

    vector<int> orders = vector<int>(N);
    for (int i = inputs.size() - 1; i >= 0; i--)
    {
        int number = i + 1;
        int j;
        for (int j = N - i -1; j > inputs[i]; j--)
        {
            orders[j] = orders[j - 1];
        }
        orders[inputs[i]] = number;
    }

    for (int i = 0; i < N; i++)
    {
        cout << orders[i] << " ";
    }

}