백준 1015번) 수열 정렬

본문의 코드보다 더 효율적인 코드가 분명 존재합니다.

참고만 해주시면 감사하겠습니다.

코드 지적은 언제나 환영입니다.

---

풀이

문제 이해하는 것이 난해했었다.

예제 입력 1을 예로 들어보자면

2 = A[0] = B[P[0]]

3 = A[1] = B[P[1]]

1 = A[2] = B[P[2]]

이다.

 

문제에서 "배열 A가 주어졌을 때 , 수열 P를 적용한 결과가 비내림차순이 되는 수열"을 찾으라고 했기때문에

B는 비내림차순 수열이다.

따라서

 

1 = A[2] = B[P[2]] = B[0]

2 = A[0] = B[P[0]] = B[1]

3 = A[1] = B[P[1]] = B[2]

로 정리할 수 있고

 

P[i]와 B의 인덱스를 다음과 같이 매칭할 수 있다.

P[2] = 0

P[0] = 1

P[1] = 2

 

따라서 수열 P는 {1, 2, 0}이다.

 

코드

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    vector<pair<int, int>> list;

    int tc;
    cin >> tc;

    for(int i = 0 ; i < tc ; i++){
        int tmp;
        cin >> tmp;
        list.push_back(make_pair(tmp, i));
    }

    sort(list.begin(), list.end());

    int list2[tc];

    for(int i = 0 ; i < tc ; i++){
        list2[list[i].second] = i;
    }

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

    return 0;
}