[백준] 2170. 선 긋기 (Java)

 

문제

2170번: 선 긋기

 

알고리즘

정렬, 스위핑

 

풀이

좌표를 x를 기준으로 정렬하면 현재 좌표가 그어진 선보다 x 값이 크거나 같은 것이 보장되기 때문에

그어진 선의 x 값을 신경쓰지 않고 계산을 할 수 있다.

 

따라서 다음 세 가지를 고려하며 선분의 길이를 늘려주면 된다.

1. 포함되는 경우

2. 일부 겹치는 경우 

3. 아예 겹치지 않는 경우

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int N = Integer.parseInt(br.readLine());
		List<Line> lineList = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			lineList.add(new Line(x, y));
		}
		Collections.sort(lineList);
		
		int end = Integer.MIN_VALUE;
		int length = 0;

		for(Line line : lineList) {

			// 포함되는 경우
			if(line.y <= end) {
				continue;
			}
			// 일부 겹치는 경우
			else if(line.x < end) {
				length += line.y-end; 
				end = line.y;
			}
			// 아예 겹치지 않는 경우
			else if(line.x >= end) {
				length += line.y - line.x;
				end = line.y;
			}
		}
		
		System.out.println(length);
	}

	static class Line implements Comparable<Line> {
		int x, y;

		public Line(int x, int y) {
			this.x = x;
			this.y = y;
		}

		@Override
		public int compareTo(Line o) {
			return x - o.x;
		}
	}
}