[백준알고리즘] 1015번: 수열 정렬 -C++

[백준알고리즘] 1015번: 수열 정렬 -C++

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

1015번: 수열 정렬

이번 문제는 이해하는데 어려움이 있었다.

 

문제를 이해하면 푸는 건 쉽게 풀 수 있는 유형이었다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

먼저, 문제를 이해한 내용에 대해 얘기해봐야겠다.

 

유독 문제를 이해하지 못했는데.. 문제에서 요구하는 것은 다음과 같다.

• 배열 \(A\)가 주어진다.
• 배열 \(A\)에 대해서 배열 \(B\)와 수열 \(P\)는 다음과 같은 관계를 갖는다.
  • \(A[i] = B[P[i]]\)
• 이때 배열 \(B\)가 비내림차순이 되도록 하는 수열 \(P\)를 찾아야 한다.
  • \(B\)가 비내림차순의 배열
  • 찾아야 하는 것은 \(P\)

 

\(P\)가 비내림차순이라는 것인지.. \(B\)가 비내림차순이라는 것인지... 이해할 수 없었는데 어쩌다 보니 이해했고 문제를 풀 수 있었다.

 

---

 

위의 문제 해석을 이해했으면 예제를 통해서 더 확실히 알 수 있다. 배열 \(A\)가 \(\{2, 3, 1\}\)일 때의 예를 통해 확인해보겠다.

• \(A[0] = 2 = B[P[0]]\)
• \(A[1] = 3 = B[P[1]]\)
• \(A[2] = 1 = B[P[2]]\)

 

여기서, 배열 \(B\)는 비내림차순의 배열이기 때문에 배열 안의 값은 \(\{1, 2, 3\}\) 일 것이다.

• \(B[P[2]] = 1 = B[0]\)
• \(B[P[0]] = 2 = B[1]\)
• \(B[P[1]] = 3 = B[2]\)

 

위와 같이 된다면 배열 \(P\)와 \(B\)의 인덱스를 매칭 시킬 수 있다.

• \(P[2] = 0\)
• \(P[0] = 1\)
• \(P[1] = 2\)

 

따라서 수열 \(P\)는 다음과 같다. $$P = \{1, 2, 0\}$$

 

---

 

위의 방식대로 푼 C++ 코드다.

#include <iostream>
#include <vector>
#include <algorithm>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	solve();
}

void solve(void)
{
	int size;
	std::cin >> size;

	std::vector<std::pair<int, int>> val_index;
	for (int i = 0; i < size; i++)
	{
		int a_val;
		std::cin >> a_val;
		val_index.push_back(std::make_pair(a_val, i));
	}

	std::sort(val_index.begin(), val_index.end());

	std::vector<int> p(size);
	for (int i = 0; i < size; i++)
		p[val_index[i].second] = i;

	for (auto a : p)
		std::cout << a << ' ';
}