[백준] 1015 수열 정렬 with C++

문제설명

---

입출력 예제

---

개념

　원본 수열에서 정렬을 적용한 후, 각 원소가 원래 있던 위치에서 어떤 위치로 이동하였는지 확인하는 문제다. 즉, 원본 수열의 원소들이 정렬된 후의 위치 값을 찾는 문제다.

 

　유의해야 할 점은, 중복된 원소의 값을 처리하는 것이다. 이는 동일한 원소의 경우 원본 수열에서 사전순으로 앞서는 것을 출력해야 한다는 것을 의미한다. 따라서 각 원소의 값을 그 원소의 원래 위치와 함께 저장하는 pair 자료형을 사용하여 해결할 수 있다. 또한, 오름차순을 정렬할 때 정렬 후에 동일한 값의 원소들 사이의 상대적인 순서를 유지하기 위해 stable_sort를 사용해야 한다. 

---

풀이

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

bool custom(pair<int,int> p1, pair<int,int> p2)
{
    return p1.first < p2.first;
}

int main()
{
    int N;
    cin >> N;

    vector<pair<int,int>> v(N), dst(N);

    for (int i = 0; i < N; ++i)
    {
        cin >> v[i].first;
        v[i].second = i;
    }

    dst = v;
    stable_sort(v.begin(), v.end(), custom);

    for (int i = 0; i < N; ++i)
    {
        auto it = find(v.begin(), v.end(), dst[i]);
        cout << distance(v.begin(), it) << " ";
    }
}