[BOJ 백준] 공장 (7578) Java

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

 

문제 설명 : 

어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블로 연결되어 있다. 즉, A열의 임의의 기계는 B열의 유일한 기계와 케이블로 연결되어 있고, B열의 임의의 기계는 A열의 유일한 기계와 케이블로 연결되어 있다

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

공장 작업의 효율성을 위해 기계들은 짝을 맺은 순서대로 배치되지 않으며, 필요에 따라 각 열의 기계들의 순서를 바꾼 바람에 케이블은 마구 엉켜있는 상태이다. 이렇게 엉켜버린 케이블은 잦은 고장의 원인이 되기 때문에, 기계의 위치를 바꾸지 않은 상태에서 케이블을 두 기계를 잇는 직선의 형태로 만들기로 했다.

예를 들어, 위의 그림과 같이 N = 5이고, A열에 위치한 기계의 식별번호가 순서대로 132, 392, 311, 351, 231이고 B열에 위치한 기계의 식별번호가 순서대로 392, 351, 132, 311, 231이라면 케이블들의 교차 횟수 혹은 서로 교차하는 케이블 쌍의 개수는 3이 된다.

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

 

입력 :

입력은 세 줄로 이루어져 있다. 첫 줄에는 정수 N이 주어지며, 두 번째 줄에는 A열에 위치한 N개 기계의 서로 다른 식별번호가 순서대로 공백문자로 구분되어 주어진다. 세 번째 줄에는 B열에 위치한 N개의 기계의 식별번호가 순서대로 공백문자로 구분되어 주어진다.

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

 

출력 : 

여러분은 읽어 들인 2N개의 기계의 배치로부터 서로 교차하는 케이블 쌍의 개수를 정수 형태로 한 줄에 출력해야 한다.

 

예제 입력 : 

5

132 392 311 351 231

392 351 132 311 231

 

예제 출력 : 

3

 

접근법 : 

1) 어떻게 풀 것인가?

2개의 배열의 배치 순서가 꼬여있는 경우, 인덱스드트리, 세그먼트 트리를 활용하면 풀 수 있다.

 

전체적인 과정은

① 첫번째 배열에서 입력받은 값들의 id를 저장한다.

② 두번째 배열에서는 첫번째 배열의 그 값이 몇번째 순서인지 기록한다.

③ 두번째 배열에서 저장된 값을 인덱스드 트리에 넣을때 구간합 1~현재 id 까지의 합이 꼬여있는 경우이다.

 

예제의 경우 0 + 1 + 0 + 2 + 3  = 6 이 된다.

 

풀이 과정 그림 하나로 요약하면 아래와 같다.

 

2) 시간복잡도

O(N log N)으로 양호

(Java 기준 - 812ms)

 

3) 공간복잡도

 식별번호 최대치 100만으로 양호함.

 

4) 풀면서 놓쳤던점

특별히 없음.

 

5) 이 문제를 통해 얻어갈 것

세그먼트 트리 or 인덱스드트리 활용. 분할정복 형태로 세그먼트 트리 풀기

 

Java 코드 : 

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

//7578 공장
public class Main {

	static int N;
	static long ans;
	static int[] factory;
	static int[] num;
	static long[] tree;

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

		N = Integer.parseInt(br.readLine());

		factory = new int[N + 1];
		tree = new long[N*4+10];
		num = new int [1000001];	// 최대치
		
		int tmp;
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			tmp = Integer.parseInt(st.nextToken());
			num[tmp] = i;
		}
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			tmp = Integer.parseInt(st.nextToken());
			factory[i] = num[tmp];
		}

		ans = 0;
		int val;
		for (int i = 1; i <= N; i++) {
			val = factory[i];
			
			// val보다 큰 인덱스 중 방문한 적 있는 인덱스의 개수를 더함
			ans += sum(1, N, 1, val + 1, N);

			// val를 방문했다는 의미로 1을 더해 줌.+ val이 포함된 구간합도 추가
			update(1, N, 1, val, 1);
		}

		bw.write(ans + "\n");
		bw.flush();
		bw.close();
		br.close();
	}

	public static long sum(int start, int end, int node, int left, int right) {
		if (end < left || right < start) {
			return 0;
		}

		if (left <= start && end <= right) {
			return tree[node];
		}

		int mid = (start + end) / 2;
		return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
	}

	public static void update(int start, int end, int node, int id, int diff) {
		if (id < start || id > end) {
			return;
		}

		tree[node] += diff;

		if (start != end) {
			int mid = (start + end) / 2;
			update(start, mid, node * 2, id, diff);
			update(mid + 1, end, node * 2 + 1, id, diff);
		}
	}

}