[백준] 공장(7578) Java

문제 링크

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

 

문제 요약

2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다.

A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블로 연결되어 있다. 즉, A열의 임의의 기계는 B열의 유일한 기계와 케이블로 연결되어 있고, B열의 임의의 기계는 A열의 유일한 기계와 케이블로 연결되어 있다

또한, 각 기계에는 식별번호가 붙어있으며, 짝이 맺어진 기계끼리는 같은 식별번호가 붙어있다. 즉, 각 열에 있는 N개의 기계끼리는 서로 다른 식별번호를 가지고 있으며, 반대쪽 열에 있는 같은 식별번호를 가진 기계와 케이블로 이어져 있다.

기계들은 아래 그림과 같이 식별번호 순서, 혹은 짝을 맺은 순서대로 배치되지 않는다.

위의 그림과 같은 입력일 때 케이블들의 교차 횟수는 3이 된다.

정수 N과 A열에 위치한 기계, B열에 위치한 기계의 식별번호가 각각 순서대로 주어질 때에 서로 교차하는 케이블 쌍의 개수를 정확하게 세어 출력하는 프로그램을 작성하시오.

 

입력

입력은 세 줄로 이루어져 있다.

첫 줄에는 정수 N이 주어진다.

두 번째 줄에는 A열에 위치한 N개 기계의 서로 다른 식별번호가 순서대로 공백문자로 구분되어 주어진다.

세 번째 줄에는 B열에 위치한 N개의 기계의 식별번호가 순서대로 공백문자로 구분되어 주어진다.

단, 1 ≤ N ≤ 500,000이며, 기계의 식별번호는 모두 0 이상 1,000,000 이하의 정수로 주어진다.

 

출력

 서로 교차하는 케이블 쌍의 개수를 정수 형태로 한 줄에 출력해야 한다.

 

접근법

Inversion counting 문제의 한 종류라고 한다 (구글링 해서 알아냈다)

케이블의 교차점이 생긴다는 의미가 순서가 뒤바뀐 (inversion) 경우가 존재한다는 의미이기 떄문이라고.

그림을 보면 이해가 편하다.

 

위 그림에서 교차점이 생기는 경우를 찾아보자.

A열 기계의 index를 순서대로 1, 2, 3, 4, 5라고 하고, B열도 마찬가지로 순서대로 1~5의 index를 부여하자.

임의의 A열의 기계와 임의의 B열의 기계가 케이블로 이어져 있는 경우를 다음과 같이 (indexA, indexB) 이렇게 표현해보자.

예를 들어 기계 132의 경우 (1, 3) 이렇게 표현할 수 있다.

 

index 기준으로 교차점이 생기는 경우는 두 기계 쌍 (x, y), (w, z) 에서 x < w && y > z 인 경우이다.

즉 indexA가 더 큰데, indexB가 더 작은, 말그대로 순서가 뒤집힌 기계쌍이 존재하는 경우 교차점이 발생하는 것이다.

위 그림에서 보면 (1,3)과 (2,1), (1,3)과 (4,2), (3,4)와 (4,2) 이렇게 3개의 경우가 조건을 만족하므로 교차점이 3개임을 알 수 있다.

 

그럼 이제 문제는 이걸 어떻게 구현하냐는 거다.

위에서 설명한 내용을 그대로 구현하면 아마 배열을 사용해서 index가 역전되는 경우를 if문으로 하나 하나 비교해가며 구간합을 N번 구하는 식의 프로그램이 나올 것 같다.

시간 복잡도는 O(N!)이 될 것 같은 느낌이다. 그렇게 구현 안해봐서 모르겠다.

 

아무튼 문제의 시간 제한이 1초이고, 1 <= N <= 500,000 이기 때문에 O(N^2)이나 O(N!) 보다는 작아야한다.

하지만 Segment tree가 등장한다면 어떨까?

지금 설명할 내용은 Segement tree를 적용하는 내용은 아니지만 Segment tree에 익숙하다면 어떤 식으로 적용할 지 눈치챌 수 있을 것이다.

Segment tree의 동작 방식에 대해서는 설명하지 않았으므로, Segment tree를 모르신다면 백준 2042번을 먼저 풀어보시길 추천한다.

일단 우리가 구해야 하는 답은 교차점의 개수인 CNT이다 (그냥 변수 이름을 CNT라고 했다)

교차점은 indexA가 더 큰데, indexB가 더 작은 경우라고 했는데, 이 조건을 indexB만 고려하는 방식으로 단순화하자.

indexA를 기준으로 둬서, 1부터 시작해서 하나씩 증가시킨다면 indexA는 이전의 기계쌍의 indexA보다 항상 크기 때문에 indexA가 더 크다는 조건은 항상 만족한다.

따라서 이전의 기계쌍과 비교해서 현재의 indexB가 더 작은지만 체크하면 되는데, 바꿔 말하면 이전의 기계쌍의 indexB가 현재의 indexB보다 더 큰 경우의 개수를 CNT에 계속 누적하면 그 것이 정답이 된다는 것이다! 

1번째

indexA = 1일 때, 1이 가장 작은 index 값이므로 이 경우에는 교차점이 존재할 수 없다. 사실 그림만 봐도 선이 한개이므로 교차점이 있을 수가 없다. indexB를 봐도 이전에 확인했던 기계쌍에 대해 자기보다 indexB가 컸던 경우가 존재할 수 없다. 당연하게도 처음으로 본 기계쌍이기 떄문이다 ㅋㅋ

일단 indexB = 3에, 여기로 이어지는 선이 존재한다는 의미로 빨간색으로 표시를 해준다.

2번쨰

이제 indexA = 2 인 경우이다. 현재의 indexB = 1인데, 이전의 기계쌍에 대해서 indexB가 1보다 큰 경우가 바로 직전에 indexB = 3인 경우가 있었다. 그 사실은 indexB = 3에 빨간색으로 표시를 해 뒀기 때문에 바로 알 수 있었다.

빨간색 indexB의 개수가 1개 이므로 CNT += 1을 해준다 (이 부분이 Segment tree와 깊은 관련이 있다!)

마찬가지로 indexB = 1에 빨간색으로 표시를 해주고 넘어간다.

3번째

indexA = 3일 때, indexB = 4이다. 이 때도 위 과정을 반복한다.

이전의 기계쌍에서 indexB가 4보다 큰 경우가 없으므로 (4보다 큰 indexB 중에서 빨간색으로 표시된 경우가 없으므로) CNT가 증가하지 않는다.

indexB = 4에 빨간색으로 표시해주고 넘어간다.

4번째

indexA = 4일 때, indexB = 2이다. 이전의 기계쌍에서 indexB가 2보다 큰 경우가 2개나 있다!

CNT += 2 를 하고, indexB = 2에 빨간색으로 표시해주고 넘어간다.

5번째 (마지막)

indexA = 5, indexB = 5 인 경우이다. indexB는 5가 최대이므로 이 경우에는 CNT가 당연히 증가하지 않는다.

indexB = 5에 빨간색으로 표시하고 넘어간다.

 

이 때 CNT의 최종값인 3이 우리가 구하려는 교차점의 개수임을 알 수 있다.

 

이제 여기서 Segment tree를 어떻게 적용해야 할 지 대충 느낌이 오는 사람이 있었으면 좋겠다. 그게 아니라면 내가 설명을 좀 못한걸지도 ㅋㅋ...

위의 5번의 단계에서 우리는 총 5번의 구간합을 구했음을 알 수 있다. 현재의 indexB보다 큰 indexB중에서 빨간색으로 표시된 indexB의 개수를 전부 세서 CNT에 누적시킨 부분이다.

그런데 우리는 구간합을 구하는 전문가를 알고 있다. 바로 Segment tree이다.

 

Segment tree의 leaf 노드를 왼쪽부터 순서대로 B열의 기계의 index와 매치시킨다 (Segment tree initializing)

그리고 indexB를 빨간색으로 표시한다는 것은 indexB에 해당하는 leaf node의 값을 0에서 1로 바꾼다는 것이다 (Segment tree update)

그리고 현재 indexB보다 큰 indexB 중에서 빨간색으로 표시된 indexB의 개수를 CNT에 누적한다는 것은 Segment tree에 query해서 현재 indexB보다 큰 node에 대한 구간합을 구한다는 것이다. (Segment tree query)

 

Update와 query는 각각 O(logN)의 시간 복잡도를 가지고 있으므로, Segment tree를 적용하면 이 문제는 O(NlogN)에 풀 수 있다.

 

그림으로 살펴보자. Segment tree를 잘 이해하고 있다면 그림이 무슨 내용인지 쉽게 알 수 있으므로 부가설명은 하지 않겠다. 귀찮아서 그런거 맞다.

1번째

2번째

3번째

4번째

5번째

 

시간 복잡도

N개의 기계쌍에 대해서 Segment tree update와 query를 각각 1번씩 수행하므로 O(NlogN)

 

 

공간 복잡도

long형 Segment tree node 2N개

A열 기계의 식별자를 저장할 int 배열의 크기 N

A열 기계와 쌍이 되는 B열 기계의 index를 저장할 int형 배열 최대 1,000,000개

 

N이 최대 500,000 이므로

8 * 2 * 500,000 + 4 * 500,000 + 4 * 1,000,000 = 14,000,000 byte

대략 14MB 이므로 넉넉하다.

 

 

풀면서 놓쳤던 점

Segment tree(Indexed tree)를 어떻게 적용해야 하는지 감이 안잡혀서 구글링을 했다.

Inversion counting 관련 문제를 몇 개 풀어보면 좋을 듯 하다.

 

 

이 문제에서 얻어갈 점

Segment tree가 활용되는 방식.

Inversion counting의 예제.

사실상 dp문제에 Segment tree를 뿌린 느낌이기 때문에 dp문제를 푼 느낌.

 

 

코드

import java.util.*;
import java.io.*;

class Main
{
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int N;
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());

		int[] arrA = new int[N + 1];
		int maxId = 0;

		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++)
		{
			arrA[i] = Integer.parseInt(st.nextToken());
			maxId = Math.max(maxId, arrA[i]);
		}

		int[] pairIdx = new int[maxId + 1];
		int machineId;

		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++)
		{
			machineId = Integer.parseInt(st.nextToken());
			pairIdx[machineId] = i;
		}

		IndexedTree idxTree = new IndexedTree(N);
		
		long cnt = 0;
		int queryLeft, queryRight;
		for (int i = 1; i <= N; i++)
		{
			queryLeft = pairIdx[arrA[i]] + 1;
			queryRight = idxTree.numOfLeaves;
			cnt += idxTree.getPrefixSum(1, idxTree.numOfLeaves, queryLeft, queryRight, 1);
			idxTree.update(1, idxTree.numOfLeaves, pairIdx[arrA[i]], 1, 1);
		}

		System.out.println(cnt);

		br.close();
	}
}

class IndexedTree
{
	long[] tree;
	int numOfLeaves;

	public IndexedTree(int N)
	{
		numOfLeaves = 1;
		while (numOfLeaves < N)
			numOfLeaves *= 2;

		//1 ~ (numOfLeaves * 2 - 1) 범위
		tree = new long[numOfLeaves * 2];
	}

	public long getPrefixSum(int left, int right, int queryLeft, int queryRight, int node)
	{
		if (right < queryLeft || left > queryRight)
			return 0;

		else if (left >= queryLeft && right <= queryRight)
			return tree[node];
		
		else
		{
			long sum = 0;
			int mid = (left + right) / 2;

			sum += getPrefixSum(left, mid, queryLeft, queryRight, node * 2);
			sum += getPrefixSum(mid + 1, right, queryLeft, queryRight, node * 2 + 1);

			return sum;
		}
	}

	public void update(int left, int right, int target, long diff, int node)
	{
		if (right < target || left > target)
			return;

		if (left <= target && right >= target)
			tree[node] += diff;

		if (left != right)
		{
			int mid = (left + right) / 2;

			update(left, mid, target, diff, node * 2);
			update(mid + 1, right, target, diff, node * 2 + 1);
		}
	}
}