[C++] 코드업(codeup) 3004번 데이터 재정렬

▽문제 바로가기

https://codeup.kr/problem.php?id=3004

데이터 재정렬

---

입력

첫째 줄에 데이터의 개수 N이 입력된다. ( 1 <= N <= 50,000)

둘째 줄에 공백으로 분리되어 N개의 서로 다른 데이터가 입력된다. (값의 범위:0~500,000)

 

출력

N개의 데이터를 0 ~ N-1로 재정렬하여 출력하라.

 

문제 풀이

 

입력을 보니까 N이 최대 50,000개 까지 입력된다고 합니다. 50,000의 제곱은 2,500,000,000 25억으로 버블 정렬, 선택 정렬 등이 제한됩니다.

 

힙정렬, 퀵 정렬, 병합 정렬 등을 사용해야 합니다. 저는 STL sort함수를 사용하여 구현하였습니다. vector로 3중 데이터를 받을 수 있도록 하였습니다. <pair<int, pair<int, int> > >

 

<입력받을 데이터, 입력순서기록, 재정렬데이터> 

첫 번째 int는 데이터를 입력받을 것입니다.

두 번째 int는 입력받은 순서를 기록할 것입니다.

세 번째 int는 재정렬데이터를 넣을 것입니다.

 

예를 들어 50 23 54 24 123 이 입력되었습니다.

 

그러면 첫 번째 int에 입력받은 값이 그대로 기록됩니다.

두 번째 int에 0 1 2 3 4로 입력받은 순서를 기록합니다.

 

이후 sort함수를 이용하여 올림차순으로 정렬합니다. 정렬이 되었으니

세 번째 int에 차례대로 0 1 2 3 4 재정렬 데이터를 넣습니다.(나중에 출력용)

 

이후 sort함수를 이용하여 입력받은 순서를 기록한 두 번째 int 값을 올림차순으로 정렬합니다.

순서대로 재정렬데이터를 갖는 세 번째 int 값을 출력합니다.

 

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

//입력받은 데이터 올림차순으로 정렬
bool comp1(pair<int, pair<int, int> > a, pair<int, pair<int, int> > b){
	return a.first<b.first;
}

//입력순서를 올림차순으로 정렬
bool comp2(pair<int, pair<int, int> > a, pair<int, pair<int, int> > b){
	return a.second.first < b.second.first;
}

int main() {
    
    int a;
    scanf("%d", &a);
    //<입력받을 데이터, 입력순서기록, 재정렬데이터> 
    vector <pair<int, pair<int, int> > > arr(a);
    int n[a];
    
    for(int i=0;i<a;i++){
		scanf("%d", &arr[i].first);	//데이터 입력받음
		arr[i].second.first = i;	//입력받은 순서 기록 
    }
    
	//입력받은 데이터 올림차순으로 정렬
    sort(arr.begin(), arr.end(), comp1); 
    
    //재정렬데이터 추가
    for(int i=0;i<a;++i){
    	arr[i].second.second = i;
    }
    
    //입력순서를 올림차순 정렬
    sort(arr.begin(), arr.end(), comp2);
    
	//재정렬데이터 순서대로 출력
	for(int i=0;i<a;++i) printf("%d ", arr[i].second.second);
        
    return 0;
}