[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;
}

생각한 것을 구현해내는게 은근 힘들었던 문제.

1. 우선 sv 벡터에 원래 순서를 기억할 수 있도록 pair를 사용하여 인덱스를 기록한다.
2. 해당 sv 벡터를 sort 함수를 통해 값을 기준으로 정렬시킨다.
3. 정렬된 sv 벡터의 인덱스가 반환해줘야 하는 값이므로 새로운 v 벡터에 sv벡터의 인덱스 값(원래 순서)에 새로운 정렬된 인덱스를 기록한다.
4. v 벡터 값을 출력한다.

3번을 생각해내는게 힘들었다. 하나하나 비교해가면서 값을 출력시키는게 너무 비효율적일 것 같아서 고민했는데 음 좀 더 다른 방식을 생각해내는게 항상 너무 힘이 든다.