[백준] 2170 선 긋기 / 자바(Java)

문제

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

2170번: 선 긋기

 

---

해설

입력값의 범위가 넓어 정렬이 필요하지만 양이 너무 많아 우선순위큐를 통해 문제를 해결한다.

우선순위큐에 넣을 때 NlogN번, 하나씩 빼면서 답을 계산할때 N번으로 총 O(NlonN)만큼의 시간복잡도로 해결이 가능하다.

 

 

주의점

• 입력 값의 범위가 너무커 Long타입을 사용한다.

---

코드

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

public class Main{

	static class set implements Comparable<set>{
		long x,y;

		public set(long x, long y) {
			super();
			this.x = x;
			this.y = y;
		}

		@Override
		public int compareTo(set o) {
			return (int) (this.x!=o.x?this.x-o.x:this.y-o.y);
		}
		
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		PriorityQueue<set> pq = new PriorityQueue<>();
		for(int i=0;i<N;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			pq.add(new set(Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken())));
		}

		long ans=pq.peek().y-pq.peek().x;
		long tmpend=pq.peek().y;
		pq.poll();
		for(int i=1;i<N;i++) {
			set tmp = pq.poll();
			long start = tmp.x;
			long end = tmp.y;
			if(tmpend>end) {
				continue;
			}else if(tmpend<start){
				ans += end-start;
				tmpend = end;
			}else {
				ans += end-tmpend;
				tmpend = end;
			}
			
		}
		System.out.println(ans);
		
		
	}
}