[c++] 백준 1015 - 수열 정렬

0. [c++] 백준

https://www.acmicpc.net/problem/1015

1. 풀이

문제를 이해하기에 오래걸렸는데, 막상 이해하고나니 간단한 문제였다.

배열 P[]를 pair<int, int>로 선언을 하여 first에는 A[i]의 값을 담고, second에는 i의 값을 담아 주었다. 그러고, sort를 활용하여 first를 기준으로 배열을 정렬을 해버렸다.

그리하면, P[]은 first를 기준으로 second는 마구잡이로 섞이게 된다. 섞여있는 P[i].second의 순서대로 B[P[i].second]는 오름차순을 만족시키는 것이 된다.

즉, 이 second 순으로 새로이 번호를 매겨주면 그것이 우리가 찾는 배열의 값이 되게 된다.

밑의 코드에서는 ret[P[i].second] = i++;을 활용하여 배열을 만들었다.

+) 추가적으로 pair은 좀 자세하게 알아둘 필요가 있을 것 같다.

대충 이전의 지식을 활용해서 간단한 구현을 하였지만, sort와 pair을 유용하게 활용해도 창의적인 코드를 짤 수 있겠다는 느낌이 든다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#include<iostream> #include<algorithm>   using namespace std;   int ret[50]; pair<int, int> P[50];   void calc(int N){     for (int i = 0; i < N; i++) {         ret[P[i].second] = i;     }       for (int i = 0; i < N; i++) {         cout << ret[i] << " ";     } }   int main() {     int N;     cin >> N;     for (int i = 0; i < N; i++) {         cin >> P[i].first;         P[i].second = i;     }       sort(P, P + N);       calc(N);       return 0; }

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!