2170번: 선 긋기

Skele·2025년 4월 22일

algorithm

알고리즘 문제 풀이

목록 보기

12/21

2170번: 선 긋기

1차원 수직선 위에 선을 N번 그린다 (1 ≤ N ≤ 1,000,000).
각 선은 두 점 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000) 사이를 연결한다.
선이 겹치는 부분은 한 번만 계산한다.
모든 선을 그린 후 총 길이를 출력한다.

접근

일차원

x, y 값은 이차원이 아닌 일차원에서의 시작점과 끝점이다.

겹치는 선분은 제외된다

겹친 선분은 총 길이에 더해지지 않는다. 1~3, 2~4의 선분이 있으면 겹치는 2~3은 두번 연산되지 않고 1~4 길이 하나로 적용된다는 뜻이다.

덧 그리기

선분이 겹칠 경우, 하나의 선분으로 합쳐서 계산할 수 있다.
위의 예시처럼 1~3, 2~4를 1~4로 만드는 것이다.
따라서 선분을 하나씩 순회하면서 이전 선분과 겹친다면 합치면 된다.
다만, 겹치지 않을 경우 새로운 선분을 관리해주어야한다는 문제가 생기는데, 선분들을 시작점으로 오름차순 정렬한다면 해결할 수 있다.
이렇게 하면 "겹치지 않는 선분이 등장 = 앞으로 이전 선분과 겹칠 일이 없다"가 성립되기 때문이다.

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		input(in);
		solve();	
	}
	
	static int lines;
	static PriorityQueue<Line> pq;
	static void input(BufferedReader in) throws IOException {
		lines = Integer.parseInt(in.readLine());
		
		pq = new PriorityQueue<Line>(new Comparator<Line>() { // 시작점 오름차순 정렬
			public int compare(Line l1, Line l2) {
				if(l1.x < l2.x) return -1;
				else if(l1.x > l2.x) return 1;
				else return 0;
			}
		});
		
		for(int i = 0; i < lines; i++) {
			StringTokenizer tokens = new StringTokenizer(in.readLine());
			pq.add(new Line(Integer.parseInt(tokens.nextToken()), Integer.parseInt(tokens.nextToken())));
		}
	}
	
	static void solve(){
		Line first = pq.poll();
		int right = first.x;
		int left = first.y;
		int sum = 0;
		
		while(!pq.isEmpty()) {
			Line cur = pq.poll();
			
			if(left < cur.x) { // 겹치지 않게 되면 길이를 더하고 새롭게 선분을 설정
				sum += left - right;
				right = cur.x;
				left = cur.y;
			} else if(cur.y > left) { // 끝점 갱신
				left = cur.y;
			}
		}
		
		sum += left - right; // 마지막 선분의 길이 추가
		
		System.out.println(sum);
	}
	
	static class Line{
		int x;
		int y;
		public Line(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
}