[백준] 1615번 : 교차개수세기 - 자바(Java) , C++

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

1615번: 교차개수세기

 

문제 해석

각각 N개의 쌍으로 이루어진 2N개의 정점과 M개의 간선으로 구성된 이분 그래프가 주어집니다.

 

M은 최대 2000*1999/2 = 1999000 -> 약 2백만개

 

이때 선분끼리 서로 교차하는 총개수를 구하세요.

 

N= 5, 그림 예시

선분의 교차 조건

(A1, B1) (A2, B2)라고 했을 때 A1 < A2, B1 > B2 또는 A1 > A2, B1 < B2를 만족한다면 두 간선은 교차합니다.

 

결국 한쪽은 커져야 하고 한쪽은 작아져야 합니다.

 

예를 들어 위의 그림에서 (3,2)와(1,5)는 서로 교차합니다. 3 > 1 , 2 <5   한쪽은 크고 한쪽은 작음

 

문제 풀이 전 설계

가장 간단하게 생각해봤을 때는 주어지는 M개의 선분을 모두 교차 검사하면서 선분의 교차 조건을 만족하는지 판단하는 방법이 있습니다.

 

이는 O(M^2)의 시간 복잡도가 소요됩니다.

for(int i=0; i<M.length(); i++){
	for(int j=0; j<M.length(); j++){
		if(i==j) continue;    
		if(선분 교차 조건 만족) count++;
	}
}

 

하지만 M의 개수는 최대 2백만 개고 O(N^2)은 당연히 시간 초과가 예상됩니다.

 

시간을 줄이기 위한 방법

정렬과 메모 이제이 션 활용

 

N= 5, 그림 예시

 

1. A를 기준으로 정렬한다.

이렇게 되면 위의 그림을 예시로는 다음과 같이 정렬됩니다.

 

(1,5) (2,2) (3,2) (4,3) (5,1) (5,3)

2. 0번째부터 끝까지 반복하면서 탐색을 시작합니다.

첫 번째 수는 항상 커지고 있기 때문에 두 번째 수가 작아지는 것에만 집중합니다.

즉, 메모된 값들 중에 나보다 작은 수들의 개수를 count 합니다.

 

메모이제이션된 값이 아무것도 없는 상황입니다.

현재 5가 나왔음을 기록합니다.

 

두 번째에는 2가 나왔음을 기록합니다.

5가 나온 적이 있기 때문에 교차선이 1개 생깁니다.

 

세 번째에는 2가 나왔음을 기록합니다.

5가 나온 적이 있기 때문에 교차선이 1개 생깁니다.

 

네 번째에는 3이 나왔음을 기록합니다.

5가 나온 적이 있기 때문에 교차선이 1개 생깁니다.

 

다섯 번째에는 1이 기록됩니다.

5가 나온 적이 1번, 2가 나온적이 2번, 3이 나온적이 1번 있기 때문에 교차선이 4개 생깁니다.

 

여섯 번째에는 3이 기록됩니다.

5가 나온 적이 1번 있기 때문에 교차선이 1개 생깁니다.

 

이렇게 정답은 : 8개가 됩니다.

 

그러면 어떻게 메모이제이션을 할 것 인가?

특정 수를 기준 이전으로 모든 누적합을 ++해주어야 합니다.

 

만약 배열을 기준으로 해준다면 최악의 경우 N=2000개인 2000번 반복하며 ++을 수행해야 합니다.

 

이렇게 되면 시간 복잡도를 O(M)으로 줄여놓았지만 O(MN)이 연출됩니다.

 

200만 -> 2000번으로 시간 복잡도는 크게 개선되었지만 여전히 40억이라는 큰 수가 나오기 때문에 시간제한 2초를 통과할 수 없을 것 같습니다. ( 탐색 시간 최대 40초 예상) CPU가 1억 연산하는 시간은 대략 1초

 

우리는 결국에 5라는 수가 들어왔을 때 1의 개수, 2의 개수, 3의 개수, 4의 개수를 구해서 다 더해서 이 총합을 교차선이라고 보고 증가시킵니다. (정렬되어 있기 때문에)

 

결국 우리는 매 연산마다 배열[1~4]의 구간합과 같은 배열[1-입력값 전까지]의 구간합을 구해야 한다로 도출됩니다.

 

이를 효율적으로 관리할 수 있는 세그먼트 트리를 활용하면 문제를 해결할 수 있을 것 같습니다.  구간에 대한 연산 시간 복잡도 logN

 

코드

자바로는 메모리 해결이 불가능한 코드라서 위의 풀이와 로직이 똑같은 C++풀이를 가져왔습니다.

#include <bits/stdc++.h>
#define ll long long int
#define endl '\n'
#define INF 1e9 + 7;
using namespace std;

ll n, m, res;
ll tree[8000];
pair<ll, ll> arr[2000000];

void update(ll N, ll s, ll e, ll idx, ll val) {
	if (idx > e || idx < s)
		return;
	if (s == e) {
		if (idx == s)
			tree[N] += 1;
		return;
	}
	ll mid = (s + e) / 2;
	update(N * 2, s, mid, idx, val);
	update(N * 2 + 1, mid + 1, e, idx, val);
	tree[N] = tree[N * 2] + tree[N * 2 + 1];
}

ll query(ll N, ll s, ll e, ll l, ll r) {
	if (l > e || r < s)
		return 0;
	if (l <= s && e <= r)
		return tree[N];
	ll mid = (s + e) / 2;
	return query(N * 2, s, mid, l, r) + query(N * 2 + 1, mid + 1, e, l, r);
}

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

	cin >> n >> m;

	for (ll i = 0; i < m; i++)
		cin >> arr[i].first >> arr[i].second;

	sort(arr, arr + m);

	for (ll i = 0; i < m; i++) {
		res += query(1, 0, n - 1, arr[i].second, n - 1);
		update(1, 0, n - 1, arr[i].second - 1, 1);
	}

	cout << res << endl;

	return 0;
}

 

자바코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

public class Main_1615_교차개수세기 {

    static class Line {
        int start;
        int end;

        public Line(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return "Line{" +
                    "start=" + start +
                    ", end=" + end +
                    '}';
        }
    }

    static int[] tree;
    static int[] numbers;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = null;

        List<Line> lines = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            lines.add(new Line(start, end));
        }

        lines.sort((a, b) -> a.start - b.start);


        tree = new int[n * 4];
        numbers = new int[n];


        makeSegmentTree(0, n - 1, 1);

        int result = 0;
        for (Line cur : lines) {
            result += sum(0, n - 1, 1, cur.end, n - 1);
            update(0, n - 1, 1, cur.end - 1, 1);

        }
        System.out.println(result);
    }

    static int makeSegmentTree(int start, int end, int index) {
        if (start == end) {
            return tree[index] = numbers[start];
        }
        int mid = (start + end) / 2;
        return tree[index] = makeSegmentTree(start, mid, index * 2) + makeSegmentTree(mid + 1, end, index * 2 + 1);
    }

    static long sum(int start, int end, int index, int left, int right) {
        // 범위 밖에 있는 경우
        if (left > end || right < start)
            return 0;
        // 범위 안에 있는 경우
        if (left <= start && end <= right)
            return tree[index];
        // 그렇지 않다면 두 부분을 나누어 합을 구하기
        int mid = (start + end) / 2;
        return sum(start, mid, index * 2, left, right) + sum(mid + 1, end, index * 2 + 1, left, right);

    }

    public static void update(int start, int end, int index, int originIndex, int diff) {
        // 범위 밖에 있는경우에는 진행하지 않습니다.
        if (!(start <= originIndex && originIndex <= end)) {
            return;
        }

        // 범위 안에 있는경우에는 값을 갱신합니다.
        tree[index] += diff;

        //리프노드일 경우에는 더이상 진행x
        if (start == end)
            return;
        //리프노드가 아닌경우에는 리프노드까지 진행
        int mid = (start + end) / 2;
        update(start, mid, index * 2, originIndex, diff);
        update(mid + 1, end, index * 2 + 1, originIndex, diff);

    }

}