#743 (Div.2) B - Swaps

문제 링크 => Problem - B - Codeforces

Problem - B - Codeforces

---

홀수로 구성된 배열 A와 짝수로 구성된 배열 B가 존재할 때,

A[0] < B[0] 을 만족하도록 swap이 이루어진 갯수의 최솟값을 구하는 문제이다.

 

문제 접근 방법은 다음과 같다.

 

1. 배열 A의 원소 x에 대하여 m[x] = i 라고 설정함

 

ex ) A = [1, 3, 5, 7, 9] 에 대하여 각각 맨 앞에 숫자를 배치하도록 하기 위해 0, 1, 2, 3, 4 만큼 이동

 

2. 배열 B의 원소 x와 인덱스 i에 대하여 (x, i) 값을 담을 수 있는 벡터 v에 대하여

    v.push_back({x, i}), check[i] = 1 라고 설정한 후에 x를 기준으로 오름차순으로 정렬해줌

 

ex ) B = [4, 8, 2, 6, 10] 에 대하여 

 

정렬된 v = {(2, 2), (4, 0), (6, 3), (8, 1), (10, 4)} 가 됨

 

3. 1, 2의 세팅이 끝나면 다음과 같은 규칙을 통해 값을 결정해간다.

 

ex ) A = [1, 3, 5, 7, 9], B = [4, 8, 2, 6, 10] 에 대하여

 

(1) A[0] = 1 일 때, B[0] = 4 일 경우 swap 한 갯수는 0 개이다.

result = m[1] + min({2, 0, 3, 1, 4}) = 0, check[2] = 0 

(m[1] 는 1이 맨 앞에 배치하도록 하기 위한 이동 횟수, min({2, 0, 3, 1, 4}) 는 2, 4, 6, 8, 10 가 맨 앞에 배치하도록 이동하기 위한 횟수)

 

(2) A[0] = 3 일 때, B[0] = 4 일 경우 swap 한 갯수는 1 개이다.

result = m[3] + min({0, 3, 1, 4}) = 1, check[0] = 0

 

(3) A[0] = 5 일 때, B[0] = 8 일 경우 swap 한 갯수는 3 개이다.

result = m[5] + min({3, 1, 4}) = 3, check[3] = 0

 

여기서 A[0] = 3 => A[0] = 5 로 변경되면서 min({3, 1, 4}) 에서 0이 사라짐으로써 1이 최소값이 됨을 알 수 있다.

 

min 값을 naive하게 for문을 돌리면 O(n^2) 이므로 시간 초과가 난다.

 

이를 해결하기 위해서 2번에서 설정해둔 check[x] 를 이용한다.

 

먼저 A[0] = 3 => A[0] = 5 에서 min({0, 3, 1, 4}) => min({3, 1, 4}) 이 되는 과정에서 min값을 다음과 같이 정해준다.

 

if (minValue == v[i].second) {
	for (int j = minValue + 1; j < n; j++) {
		if (check[j]) {
			minValue = j;
			break;
		}
	}
}

 

(min + 1) 부터 (n - 1) 까지 탐색하면서 check 값이 남아있을 경우 해당 값을 min 값으로 설정해주는것이 핵심이다.

 

위 코드를 통해 min({0, 3, 1, 4}) 에서 min = 0 이므로 1 부터 4까지 탐색하면서 1은 아직 남아있으므로 min 값을 1이 된다.

 

즉, O(n) 으로 문제를 해결할 수 있다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <queue>
#include <stack>
#define endl '\n'
#define INF 1000000000
#define ll long long

using namespace std;

bool compare(pair<int, int> x, pair<int, int> y) {
	return x.first < y.first;
}

void test() {

	int n;
	cin >> n;

	map<int, int> m, check;
	vector<pair<int, int>> v;

	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		m[x] = i;
	}

	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		v.push_back({ x,i });
		check[i] = 1;
	}

	sort(v.begin(), v.end(), compare);

	int result = INF, minValue = 0;

	for (int i = 0; i < n; i++) {
		result = min(result, minValue + m[2 * i + 1]);
		check[v[i].second] = 0;
		if (minValue == v[i].second) {
			for (int j = minValue + 1; j < n; j++) {
				if (check[j]) {
					minValue = j;
					break;
				}
			}
		}
	}

	cout << result << endl;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int t;
	cin >> t;
	while (t--) test();

	return 0;
}