[C++]백준 - 1015번 문제

1015번: 수열 정렬 (acmicpc.net)

1015번: 수열 정렬

 

1015번 : 수열 정렬

---

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를 출력한다.

 

 

 

---

 

생각해 볼 점

---

문제 설명이 상당히 복잡한데..

 

입력은 배열 A가 주어지고, A를 오름차순으로 정리한 B를 만들어주는 P 배열이 있으며,

 

출력은 P 배열을 출력해야 합니다.

 

매커니즘은 위 사진과 같습니다.

 

풀이는 아래와 같이 합니다.

 

Pair<int, int>의 형태로 <A의 값, index>를 저장합니다.

아래와 같은 형태가 됩니다.

 

그 후, A의 값을 기준으로 정렬합니다. 

다 진행되면 아래처럼 됩니다.

 

이제 A의 값은 더 이상 사용하지 않을 것이므로 A[i] = 새로운 index로 변경합니다.

아래처럼 됩니다.

 

이제, 마지막으로 Index를 기준으로 정렬합니다.

 

그러면, 우리가 구하려던 P가 나오게 됩니다.

 

코드

---

#include <iostream>
#include <algorithm>

bool Sorting_by_value(const std::pair<int, int>& A, const std::pair<int, int>& B)
{
	return A.first < B.first || (A.first == B.first && A.second < B.second);
}

bool Sorting_by_index(const std::pair<int, int>& A, const std::pair<int, int>& B)
{
	return A.second < B.second;
}

int main()
{
	int N;
	scanf("%d", &N);

	std::pair<int, int> *arr = new std::pair<int, int>[N];	//A[i], P[i]
	for (int i = 0; i < N; i++)
	{
		int input;
		scanf("%d", &input);
		arr[i] = { input, i };
	}

	std::sort(arr, arr + N, Sorting_by_value);
	
	for (int i = 0; i < N; i++) arr[i].first = i;

	std::sort(arr, arr + N, Sorting_by_index);

	for (int i = 0; i < N; i++) printf("%d ", arr[i].first);

	delete[] arr;
	return 0;
}

 

그 외

---

중복값이 있을 경우, 사전 순으로 앞서는 것을 출력한다는 말을 주의하세요.

 

return A.first < B.first || (A.first == B.first && A.second < B.second);

 

빨간 칠한 부분이 괜히 있는 게 아닙니다.

 

Sort는 사전 순으로 정렬을 보장하지 않습니다. 저 부분을 빼면 틀렸다고 나올 것입니다.