BOJ - 2170 ) 선 긋기

---

 

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

2170번: 선 긋기

---

 

문제의 내용은 간단하다. -10억 ~ +10억에서 두점의 위치가 선으로 연결된 정보가 들어오는데..

 

이를 빨간 화살표방향 (위에서) 보았을때 여러번칠해진거까지 감안해서 길이를 출력하는 문제이다.

 

두점 ( A,B )라 했을때 항상 A<B 이게 입력을 받고,

 

모든 점을 배열에 넣고나서, 첫번째 선의 출발점과 끝점이 정렬되게 전체 배열을 정렬해준다.

 

그러면 배열의 0번째 부터 탐색하게되면, NOW+1 번째의 첫번째 요소는 항상 같거나 큼이 보장되고,

 

만약 정렬시 두번째요소까지 오름차순으로 정렬했다면, NOW+1번째의 첫번째점이 NOW번째의 두번째 점보다 

 

큰지? 작은지?의 여부만 확인한다면 전체 길이를 O(NlogN)에 구할수 있다.

 

Array.sort 는 Merge Sort를 이용하여 NlogN을 보장하므로 적절하게 사용한다.

 

풀다가보면은, 현재 두번쨰 좌표가 다음의 첫번째 좌표보다 작아지면 새롭게 업데이트를 해주는 방식으로 

 

배열을 탐색한다.

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.StringTokenizer;

public class boj2170 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		ArrayList<int[]> al = new ArrayList<>();
		for(int i=0;i<n;++i) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			if(s>e) {
				int t=s;
				s = e;
				e = t;
			}
			al.add(new int[] {s,e});
		}
		al.sort(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0]==o2[0]) {
					return o1[1]-o2[1];
				} else if(o1[0] >o2[0]) {
					return 1;
				} else {
					return -1;
				}
			}
		});
		int answer =0;
		int s = al.get(0)[0];
		int e = al.get(0)[1];
		for(int i=1;i<n;++i) {
			int nows= al.get(i)[0];
			int nowe= al.get(i)[1];
			if(nows<=e) {
				if(e<nowe)e=nowe;
			} else  {
				answer +=(e-s);
				s=nows;e=nowe;
			}
		}
		answer +=(e-s);
		System.out.println(answer);
	}

}

---