문제설명
입출력 예제
개념
원본 수열에서 정렬을 적용한 후, 각 원소가 원래 있던 위치에서 어떤 위치로 이동하였는지 확인하는 문제다. 즉, 원본 수열의 원소들이 정렬된 후의 위치 값을 찾는 문제다.
유의해야 할 점은, 중복된 원소의 값을 처리하는 것이다. 이는 동일한 원소의 경우 원본 수열에서 사전순으로 앞서는 것을 출력해야 한다는 것을 의미한다. 따라서 각 원소의 값을 그 원소의 원래 위치와 함께 저장하는 pair 자료형을 사용하여 해결할 수 있다. 또한, 오름차순을 정렬할 때 정렬 후에 동일한 값의 원소들 사이의 상대적인 순서를 유지하기 위해 stable_sort를 사용해야 한다.
풀이
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool custom(pair<int,int> p1, pair<int,int> p2)
{
return p1.first < p2.first;
}
int main()
{
int N;
cin >> N;
vector<pair<int,int>> v(N), dst(N);
for (int i = 0; i < N; ++i)
{
cin >> v[i].first;
v[i].second = i;
}
dst = v;
stable_sort(v.begin(), v.end(), custom);
for (int i = 0; i < N; ++i)
{
auto it = find(v.begin(), v.end(), dst[i]);
cout << distance(v.begin(), it) << " ";
}
}
반응형
'Algorithm > 백준' 카테고리의 다른 글
[백준] 2217 로프 with C++ (0) | 2024.03.08 |
---|---|
[백준] 1013 Contact With C++ (0) | 2023.08.01 |
[백준] 1004 어린 왕자 with C++ (0) | 2023.07.28 |
[백준] 1002 터렛 with C++ (0) | 2023.07.20 |
[백준] 1094 막대기 with C++ (0) | 2023.07.04 |