백준 1015 풀이

링크텍스트

처음에는 그냥 생각없이 입력받은 A를 정렬하고 P배열의 값을 index로 치환해주는 식으로 단순하게 풀이를 했다.

for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i] == arr1[j] && arr[j] != -1) {
				arr[j] = -1;
				p[j] = i;
			}
		}
	}

저렇게 풀었는데 정답이 나올리가...

당연히 틀렸다.
무엇이 문제인지 생각해봤는데 결국 핵심은 A[i] = B[j]인 것이고 j=P[i]라는 점이다.

문제에 나온 예시로 이야기하면

2 3 1을 입력받았을 때 이를 정렬하면 1 2 3이 된다. A->B로 정렬되면서 인덱스의 변화는 0 1 2 에서 2 0 1이 된다. 또한 B만 기준으로 보면 1 2 3에 대한 인덱스는 0 1 2가 된다. 이 인덱스 값은 P배열과 같다.

잘 이해가 안된다.

A[i] = B[P[i]].
여기서 정렬한 A의 (값, 인덱스) 쌍은 (1,2) (2,0) (3,1)이고 B는 (1,0) (2,1) (3,2)이다.
값은 1 2 3으로 같으니 조건은 만족한다. 해답은 여기서 나온다.

A의 인덱스가 P배열의 값을 결정할 수 있다.

따라서 (정렬한 A의 인덱스, B의 인덱스(P배열의 값)) 이렇게 쌍을 만들어 정렬을 하면 우리가 찾는 P배열이 나온다.(i=0일때, A[0]=2, B[?]가 2가 되기위해서는 ?가 1이어야 한다. 즉 P[0] = 1이다.)

(2,0) (0,1) (1,2)라는 쌍이 나오고 쌍의 처음은 P의 인덱스가 되고 뒤는 P배열의 값이 된다.
정렬하면 (0,1) (1,2) (2,0)이 되고 P배열의 값은 1 2 0이 된다.

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <utility>
using namespace std;

int main() {
	int answer = 0;
	int n;
	int arr[50];

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int arr1[50];
\
	copy(arr, arr + n, arr1); //A
	sort(arr, arr+n); //B

	int p[50];

	vector<pair<int,int>> v;
	for (int i = 0; i < n; i++) {
		pair<int, int> p = make_pair(arr1[i], i);
		v.push_back(p);
	}
	sort(v.begin(), v.end());
		
	vector<pair<int, int>> B;
	for (int i = 0; i < n; i++) {
		pair<int, int> p = make_pair(v[i].second, i);
		B.push_back(p);
	}
	sort(B.begin(), B.end());

	for (int i = 0; i < n; i++) {
		cout << B[i].second << ' ';
	}
}