[백준알고리즘] 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 << ' ';
}