[BOJ Java] 백준 2170번: 선 긋기

 📚 문제

[BOJ Java] 백준 2170번: 선 긋기 
https://www.acmicpc.net/problem/2170

 

---

 📝 입력 및 출력

---

 🔎 문제 풀이

• 선분의 양 끝 점을 입력받고, 시작점($x$)을 기준으로 오름차순 정렬한다. 만약 시작점($x$)이 같다면 끝점($y$)을 기준으로 정렬한다.

list.sort((list1, list2) -> { // x 순으로 정렬.
	if (list1[0] == list2[0])
		return list1[1] - list2[1];
	return list1[0] - list2[0];
});

 

정렬은 위 코드와 같이 람다식으로 구현했다. 시작점이 같으면 끝점을 기준으로 정렬하는 것이다.

 

• 첫 번째 선분의 양 끝을 변수로 저장해 두고, 입력된 선분들을 순회하며 범위를 확장한다. 다음 선분이 이전 선분 중간에서 시작하면 범위가 겹치므로 끝점이 뒤로 더 밀려난다. 즉, 새로운 선분의 시작점($i[0]$)이 이전 선분의 양 끝(left, right) 사이에 있으면 right를 새로운 끝점($i[1]$)과 기존 점(right) 중 더 큰 값으로 갱신한다. 
• 만약 새로운 선분의 시작점이 기존 범위 내부에 없다면 선분이 끊기는 것이므로 현재까지의 선분 길이를 저장해 두고 양 끝 범위를 수정한다.

---

 ⌨️ Java 코드

 

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		List<int[]> list = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
			list.add(new int[] { x, y });
		}
		list.sort((list1, list2) -> { // x 순으로 정렬.
			if (list1[0] == list2[0])
				return list1[1] - list2[1];
			return list1[0] - list2[0];
		});
		int left = list.get(0)[0], right = list.get(0)[1], rst = 0;
		for (int[] i : list) {
			if (left <= i[0] && i[0] <= right) // 오른쪽으로 확장.
				right = Math.max(right, i[1]);
			else if (right <= i[0]) { // 끊기면 길이 저장하고 범위 이동.
				rst += right - left;
				left = i[0];
				right = i[1];
			}
		}
		rst += right - left;
		System.out.println(rst);
	}
}