[백준] 7578: 공장 - JAVA

01 Dec 2023 in Algorithm on 자료 구조

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

풀이

A열과 B열에 같은 숫자들을 연결할 때, 케이블들이 서로 교차하는 부분의 개수를 세는 문제이다.

A열: 1 2 3 4 5

B열: 2 4 1 3 5

위와 같이 주어졌을 때, B열에서 A열로 줄을 쏴주었다.

B열의 2에서 A열의 2로 줄을 쐈을 때, A열의 2보다 오른쪽에 이미 연결된 점이 있다면 그 점이 교차하는 점이다.

B열은 앞에서부터 순서대로 보는데, A열의 연결된 점 오른쪽으로 연결된 점이 있다는 것은 B열의 앞쪽 점과 연결되어 있다는 것이므로 교차한다는 것이다.

A열의 인덱스를 저장해주었고, B열의 점이 A열의 어떤 인덱스와 연결되는지 저장했다.

세그먼트 트리를 이용해 A열의 인덱스부터 N까지 구간합을 구해 교차점이 몇개인지 구하고, 방문한 점을 1로 바꿔주었다.

---

메모리: 108248KB

시간: 808ms

언어: Java 11

코드

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

public class Main {
    static class SegmentTree {
        long[] tree;

        public SegmentTree(int arrSize) {
            int height = (int) Math.ceil(Math.log(arrSize) / Math.log(2)) + 1;
            tree = new long[(1 << height)];
        }

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

            tree[node] += diff;

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

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

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

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[1_000_001]; // 첫번째 줄 숫자의 인덱스를 저장
        for (int i = 1; i < N + 1; i++) {
            arr[Integer.parseInt(st.nextToken())] = i;
        }

        st = new StringTokenizer(br.readLine());
        int[] index = new int[N + 1]; // 두번째 줄 숫자가 첫번째줄에서 어디에 위치해있는지
        for (int i = 1; i < N + 1; i++) {
            index[i] = arr[Integer.parseInt(st.nextToken())];
        }

        SegmentTree seg = new SegmentTree(N);

        long ans = 0;
        for (int i = 1; i < N + 1; i++) {
            // 줄 연결하고 해당 인덱스부터 오른쪽으로 볼 때 연결된 선이 있는지 확인
            ans += seg.sum(1, 1, N, index[i], N);
            // 연결한 줄 1로 바꿔서 방문처리
            seg.update(1, 1, N, index[i], 1);
        }

        System.out.println(ans);
    }
}