1015-수열정렬

www.acmicpc.net/problem/1015

1015번: 수열 정렬

본 문제는 차례로 입력받은 원소를 저장하는 배열 A를 오름차순(=비내림차순)으로 정렬하기 위하여, 배열 A의 각 원소를 몇 번째 인덱스에 배치해야하는지를 찾는 문제입니다. 

 

예제로 A = {2, 3, 1}이라는 배열이 주어졌을때, A의 원소 "2", "3", "1"을 오름차순이 되도록 배치시켜 재배치(A) = {1, 2, 3}이 되도록 배열의 원소를 재배치해야 합니다. 여기서, 재배치( )는 입력 받은 행렬을 오름차순으로 바꾸어주는 함수로 생각하시면 됩니다.

 

그렇다면, A를 오름차순으로 만들기 위해서 "2"은 배열의 두번째 인덱스(1)에 배치, "3"는 배열의 세번째 인덱스(2)에 배치, "1"은 배열의 첫번째 인덱스(0)에 배치해야합니다. 고로 정답은 {1, 2, 0}이 되는 것입니다.

 

저는 이를 구현하기 위하여 pair 자료구조를 사용하였습니다. 먼저, first에는 원소값을, second에는 인덱스값을 저장하였습니다. 그리고 이를 배열처럼 표현하기위하여 vector 자료구조를 사용하여 저장해주었습니다.

 

이후 first를 기준으로 배열을 오름차순으로 정렬하였습니다. 정렬이 되도 각 원소(pair)의 second값에는 정렬되기 이전에 인덱스 값이 저장되어 있습니다. 이를 사용하면 정렬되고 난 후에 해당 원소의 인덱스 값과 정렬되기 이전에 인덱스 값을 알 수 있습니다. 정렬된 배열의 i번째 원소가 정렬 이전에 몇 번째 인덱스에 위치했는지를 테이블에 역으로(테이블[정렬되기 이전 인덱스]=정렬된 후 인덱스) 기록하였습니다. 이렇게 기록하면 정렬되기 전 배열의 i번째 원소가 오름차순으로 정렬되기 위해 몇번째 인덱스에 위치해야하는지가 기록됩니다. 최종적으로 해당 테이블의 원소를 순서대로 출력하였습니다.

코드

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

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

    vector<pair<int,int>> A(N);
    vector<int> P(N); 
    
    for(int i = 0; i < N; i++)
    {
        cin >> A[i].first;
        A[i].second = i;
    }

    sort(A.begin(), A.end());
    
    for(int i = 0; i < N; i++) P[A[i].second] = i;
    for(int i = 0; i < N; i++) cout << P[i] << " ";

    return 0;
}