[JAVA] 백준 (골드5) 2170번 선 긋기

링크

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

---

입력 예제

4
1 3
2 5
3 5
6 7

---

출력 예제

5

---

풀이

여러 개의 선분이 주어질 때 겹치는 구간을 고려하여 전체 선분의 길이를 구해야 한다. 우선 입력 예제에서 생각해보면 첫 번째 선분은 (1, 3)이 되고 다음 좌표를 보면 (2, 5)이기 때문에 기존 선분을 연장한 (1, 5)가 된다.

이때 기존 선분의 끝점을 기준으로 다음 좌표의 시작점을 비교하여 기존 선분의 여부를 결정하면 된다. 다음 좌표는 (3, 5)으로 기존 선분의 끝점인 5보다 시작점이 작으므로 기존 선분은 그대로 유지된다.

하지만 다음 좌표는 (6, 7)으로 기존 선분의 끝점인 5보다 크므로 새로운 선분으로 갱신하게 된다. 이때 새로운 선분이 생길 때 기존 선분의 길이는 누적해간다.

for (int i = 1; i < N; i++) {
    int x1 = list.get(i)[0];
    int x2 = list.get(i)[1];
    if (x1 > end) {  //끝점보다 클 경우 새로운 선분
        total += end - start;  //기존 선분 길이 추가
        //새로운 선분
        start = x1;
        end = x2;
    } else {  //기존 선분일 경우 끝점 갱신
        end = Math.max(end, x2);
    }
}

전체 코드

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

/*
백준 / 선 긋기 / 골드5
https://www.acmicpc.net/problem/2170
 */
public class BOJ_2170 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        List<int[]> list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            list.add(new int[]{x, y});
        }

        //두 점의 좌표(x1, x2)에서 x1 오름차순 정렬, x1이 같다면 x2는 오름차순 정렬
        list.sort(Comparator.comparingInt((int[] o) -> o[0])
                .thenComparingInt((int[] o) -> o[1]));

        //첫 번째 좌표로 초기화
        int start = list.get(0)[0];
        int end = list.get(0)[1];
        int total = 0;

        for (int i = 1; i < N; i++) {
            int x1 = list.get(i)[0];
            int x2 = list.get(i)[1];
            if (x1 > end) {  //끝점보다 클 경우 새로운 선분
                total += end - start;  //기존 선분 길이 추가
                //새로운 선분
                start = x1;
                end = x2;
            } else {  //기존 선분일 경우 끝점 갱신
                end = Math.max(end, x2);
            }
        }

        total += end - start;  //마지막 선분 길이 추가
        System.out.println(total);
    }
}