Baekjoon 2170 선 긋기 JAVA

2170번: 선 긋기

문제

매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

입력

첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

출력

첫째 줄에 그은 선의 총 길이를 출력한다.

풀이

선을 그을때 그어지는 선은 계속 겹쳐진다. 

먼저 선을 긋는 시작점을 기준으로 정렬을 한다. 단, 시작점이 동일하다면 끝점을 기준으로 정렬을 하여

선을 긋는 구간이 오름차순이 되도록한다.

 

선을 그으면서 두 점의 위치가 이미 긋고 있는 선보다 밖에 있다면 이전에 그렸던 선의 값을 따로 더해서 그은 선에 대한 정보를 저장한다.

시작점의 위치가 기존에 존재하는 선밖에 범위이기에 새로운 선의 시작이기에, 다시 범위안에 있는 선을 판단하는 과정을 마지막 점까지 반복해서 총 그어지는 선의 길이를 구한다.

코드

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

public class Main {
	static class line implements Comparable<line>{
		int s,e;
		@Override
		public int compareTo(line o) {	// 시작점을 기준으로 오름차순 정렬
			if(this.s==o.s)	// 시작점이 동일하면 끝점을 기준으로 오름차순 정렬
				return this.e-o.e;
			return this.s-o.s;
		}
		public line(int s, int e) {
			this.s = s;
			this.e = e;
		}		
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine()), ans=0;
		line [] lines = new line[n];
		for(int i=0;i<n;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			lines[i]=new line(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		Arrays.sort(lines);	// 1. 끝점 기준 오름차순 정렬, 2. 시작점기준 오름차순 정렬 
		int l=lines[0].s, r=lines[0].e;	// 정렬을 했기에 0번째가 가장 처음에 시작하는 위치
		for(int i=0;i<n;i++) {
			if(r<lines[i].s) {	// 다음 시작점이 선을 긋는 위치를 벗어났다면 새로운 선분이기에 긋고 있던 선의 길이를 저장
				ans+=r-l;	// 현재까지 긋던 선의 길이를 저장
				l=lines[i].s;	// 새로운 시작점
				r=lines[i].e;	// 새로운 끝점
			}
			else if(lines[i].s<=r)	// 시작점의 길이가 끝점보다 작다면 현재 긋는 선의 한점에서 시작되기에 
				r=Math.max(r,lines[i].e);	// 현재 긋는 선의 길이를 연장 혹은 그 안에서 해결
		}
		System.out.println(ans+r-l);	// 마지막에 그은 선의 길이를 저장
	}
}