[백준] 2170번: 선 긋기

문제

백준 - 2170번: 선 긋기

분석

N개의 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어지고, 그려진 선의 총 길이를 구하는 문제이다. (겹쳐진 곳은 중복으로 길이에 포함하지 않는다.)

시작점을 기준으로 정렬이 된다면, 중간에 선분을 잇는다든지 복잡한 경우를 생각하지 않아도 된다. 기존 선이 있고 새로운 선을 그을 경우는 세 가지로 생각해 볼 수 있다.
1.기존 선에서 일부가 겹쳐 연장될 때
2.기존 선에 새로운 선이 포함될 때
3.기존 선과 하나도 안 겹칠 때

위의 알고리즘을 구현하려면 선분을 두 개를 놓고 비교해야 한다.
또한, 시작점을 기준으로 정렬된 상태가 필요하기 때문에 우선순위큐를 사용하고 두 선분을 poll()하여 비교한다.

코드에서는 1과 2를 하나로 묶어 표현할 수 있다.
새로운 시작점이 기존 선분 안에 들어가면 기존 선과 새로운 선 둘 중 더 큰 끝점을 채택하여 합쳐진 선분을 다시 우선순위큐에 넣는다.
3일 경우에는, 기존 선분은 길이를 계산하여 총 길이에 반영한다. 새로운 선분은 다시 우선순위큐에 넣는다.

마지막에는 우선순위큐에 선분 하나만 남게 되고, 해당 선분의 길이를 총 길이에 반영해 주면 된다.

우선순위큐에서 poll()이나 add()연산은 O(logN)이고 해당 작업을 N-1번 반복하기 때문에 O(NlogN)이 시간 복잡도이다.

코드

해결언어 : Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static PriorityQueue<int[]> pq;
	static int ans;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		pq = new PriorityQueue<>((o1, o2) -> {
			if (o1[0] == o2[0])
				return o1[1] - o2[1];
			return o1[0] - o2[0];
		});
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			pq.add(new int[] { x, y });
		}
		while (pq.size() > 1) {
			int[] val = pq.poll();
			int[] val2 = pq.poll();
			int x = val[0], y = val[1];
			int x2 = val2[0], y2 = val2[1];
			if (x <= x2 && x2 <= y) {
				pq.add(new int[] { x, Math.max(y, y2) });
			} else {
				ans += y - x;
				pq.add(val2);
			}
		}
		ans += pq.peek()[1] - pq.peek()[0];
		System.out.println(ans);
		br.close();
	}

}