백준 7578 공장 C++

https://www.acmicpc.net/problem/7578

7578번: 공장

주어진 A, B에 대해 같은 수끼리 이었을 때 교차점이 몇 개인지를 구하는 문제입니다.

 

예전에 풀었던 문제와 비슷하여 동일한 방식으로 풀었습니다.

https://ghqls0210.tistory.com/152

백준 / 1517 버블 소트 C++

 

1517번 문제의 경우, 주어진 수열을 버블 소트할 때 스왑이 몇 번 일어나는 지를 구하는 문제였고, 이것을 inversion counting으로 바꿔 문제를 풀면, 머지 소트 과정에서 생기는 교차점의 개수와 동일합니다.

 

이 방법을 7578번에 적용한다면, B의 입력으로 들어온 것을 머지 소트가 된 값으로 생각을 하면 됩니다.

그렇기에 B의 입력으로 들어온 값을 순차적으로 0,1,2,... 라는 새로운 번호를 부여하고 이를 다시 A에 대입하면 (A에는 겹치는 값 없음) 2,0,1,.... 과 같이 무작위 배열 같은 것을 머지소트를 이용해 오름차순으로 정렬하는 것과 동일합니다. 

 

결국 최종적으로 구하는 교차점의 개수와 머지소트 과정에서 발생하는 교차점의 개수가 동일한 것을 가리키므로 답을 구할 수 있습니다.

 

코드는 다음과 같습니다.

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

using namespace std;

int n;
int arr[500001];
int tmp[500001];
long long result = 0;

void init()
{
	cin >> n;

    int chk[1000001];
  
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		arr[i] = num;
        chk[num] = i;
	}

    // B에 입력된 값에 0부터 부여
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        int idx = chk[num];
        arr[idx] = i;
    }
}

void merge(int start, int last)
{
	int mid = (start + last) / 2;
	int i = start;
	int j = mid + 1;
	int k = start;
	int cnt = 0;

	while (i <= mid && j <= last) {
		// 왼쪽 배열의 값이 정렬될 때
		if (arr[i] <= arr[j]) {
			tmp[k++] = arr[i++];
			result += (long long)cnt;
		}
		// 오른쪽 배열의 값이 정렬될 때
		else {
			tmp[k++] = arr[j++];
			cnt++;
		}
	}

	// 남은 부분 중 오른쪽 배열의 값이 정렬될 때
	if (i > mid) {
		int s = j;
		while (s <= last) {
			tmp[k++] = arr[s++];
			cnt++;
		}
	}
	// 남은 부분 중 왼쪽 배열의 값이 정렬될 때
	else {
		int s = i;
		while (s <= mid) {
			tmp[k++] = arr[s++];
			result += (long long)cnt;
		}
	}

	for (int t = start; t <= last; t++)
		arr[t] = tmp[t];
}

void mergesort(int start, int last)
{
	if (start < last) {
		int mid = (start + last) / 2;
		mergesort(start, mid);
		mergesort(mid + 1, last);
		merge(start, last);
	}
}

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

	init();
	mergesort(0, n - 1);
	cout << result;
}