[C++] 백준 1015 : 수열 정렬
#include <iostream>
#include <utility> // pair
#include <algorithm> // sort
#include <vector>
using namespace std;
int N, x;
vector<pair<int, int> > sv;
int main(int argc, char** argv){
scanf("%d", &N);
for(int i=0; i<N; i++){
scanf("%d", &x);
sv.push_back(make_pair(x, i)); // 값, 인덱스 - 원래 순서 기억
}
sort(sv.begin(), sv.end()); // 값 기준 정렬
vector<int> v(N);
for(int i=0; i<N; i++){
v[sv[i].second] = i; // 정렬된 인덱스 할당
}
for(int i=0; i<N; i++){
printf("%d ", v[i]);
}
return 0;
}
생각한 것을 구현해내는게 은근 힘들었던 문제.
- 우선 sv 벡터에 원래 순서를 기억할 수 있도록 pair를 사용하여 인덱스를 기록한다.
- 해당 sv 벡터를 sort 함수를 통해 값을 기준으로 정렬시킨다.
- 정렬된 sv 벡터의 인덱스가 반환해줘야 하는 값이므로 새로운 v 벡터에 sv벡터의 인덱스 값(원래 순서)에 새로운 정렬된 인덱스를 기록한다.
- v 벡터 값을 출력한다.
3번을 생각해내는게 힘들었다. 하나하나 비교해가면서 값을 출력시키는게 너무 비효율적일 것 같아서 고민했는데 음 좀 더 다른 방식을 생각해내는게 항상 너무 힘이 든다.
Author And Source
이 문제에 관하여([C++] 백준 1015 : 수열 정렬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lamknh/C-백준-1015-수열-정렬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)