[Baekjoon/C++] 1015번 - 수열 정렬

Baekjoon Online Judge

문제로 이동

 

문제

P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.

배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.

 

입력

첫째 줄에 배열 A의 크기 N이 주어진다. 둘째 줄에는 배열 A의 원소가 0번부터 차례대로 주어진다. N은 50보다 작거나 같은 자연수이고, 배열의 원소는 1,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 비내림차순으로 만드는 수열 P를 출력한다.

 

---

예제 입력	예제 출력
3 2 3 1	1 2 0
4 2 1 3 1	2 0 3 1
8 4 1 6 1 3 6 1 4	4 0 6 1 3 7 2 5

---

풀이

#include <iostream>
#include <algorithm>
using namespace std;

struct element {
	int num; // 원소
	int idx1; // 원소 입력 순 인덱스
	int idx2; // 크기 순 인덱스
};

// 정렬 - 오름차순
bool compare1(element a, element b) {
	return a.num < b.num;
}

// 정렬 - 되돌리기
bool compare2(element a, element b) {
	return a.idx1 < b.idx1;
}

element arr[51];

int main() {
	int N; // 배열 A의 크기 N
	cin >> N;

	// 입력
	for (int i = 0; i < N; i++) {
		cin >> arr[i].num;
		arr[i].idx1 = i;
	}

	// 입력한 숫자를 오름차순으로 정렬
	stable_sort(arr, arr + N, compare1);

	// 각 숫자의 현재 인덱스를 입력
	for (int i = 0; i < N; i++)
		arr[i].idx2 = i;

	// 오름차순으로 정렬한 배열을 되돌리기
	stable_sort(arr, arr + N, compare2);

	// 출력
	for (int i = 0; i < N; i++)
		printf("%d ", arr[i].idx2);
	cout << endl;

	return 0;
}

입력된 수열을 오름차순으로 정렬했을 때의 인덱스를 처음 입력된 수열의 순서에 맞춰 출력해야하는 문제이다.

입력 : 2 3 1

정렬 : 1 2 3
idx  : 0 1 2

출력 : 1 2 0

 

이를 구현하기 위해 입력된 값, 입력될 때의 순서(인덱스), 정렬한 뒤의 인덱스를 저장할 수 있는 구조체 element를 구현했다. 그 뒤 이 구조체로 선언한 배열을 오름차순으로 정렬해주는 compare1과 입력한 순으로 되돌리는 compare2를 구현한 뒤 stable_sort()를 통해 정렬했다.

 

sort()는 정렬 후에 입력된 순서대로 저장되어 있다는 보장이 없기에 sort() 대신 stable_sort()를 사용해야 한다.