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

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

1015번: 수열 정렬

---

이게 도대체 무슨 문제인가.... 이해가 안되니까 시간이 좀 걸렸다. 물론 이해를 하면 바로 풀 수 있다.

어쨋든 B[P[i]] = A[i]를 사용해야 한다. 

• B[P[0]] = (A[0] = 2)
• B[P[1]] = (A[1] = 3)
• B[P[2]] = (A[2] = 1)

배열 B를 오름차순으로 정렬한다.

• B[P[2]] = 1
• B[P[0]] = 2
• B[P[1]] = 3

위 과정을 통해 배열 B = {1, 2, 3}이 된다. 여기서 얻을 수 있는 정보는 다음과 같다.

• P[2] = 0
• P[0] = 1
• P[1] = 2

배열 P = {1, 2, 0}을 얻게 된다. 이제 배열 P에 담긴 value를 출력하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

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

    int n;
    cin >> n;

    int a[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];

    vector<pair<int, int> > b;
    for (int i = 0; i < n; i++)
        b.push_back(make_pair(a[i], i));
    sort(b.begin(), b.end());

    vector<pair<pair<int, int>, int> > bp;
    for (int i = 0; i < n; i++)
        bp.push_back(make_pair(make_pair(b[i].first, b[i].second), i));
    sort(bp.begin(), bp.end(), compare);

    for (int i = 0; i < n; i++)
        cout << bp[i].second << " ";
}