문제

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

이해

1차원 좌표계 상에서 선을 긋는다. 선은 같은 곳을 여러 번 그을 수 있지만 1차원 좌표계이기 때문에 한 번 그은 곳과 차이는 구별할 수 없다.

즉, (1, 3), (2, 4)를 그었을 때 선은 (1, 4)가 된다.

N번 선을 그었을 때 선의 총 길이를 출력하자.

접근

본 문제는 스위핑 알고리즘의 대표적인 유형이다. 스위핑 알고리즘이란 한 쪽 방향부터 시작해서 하나씩 스캔하면서 처리하는 알고리즘을 의미한다. "쓸다"의 의미처럼 한 쪽부터 하나씩 읽어가면서 분기처리하면 된다. 순차적으로 데이터를 처리한다는 구조라는 점에서 슬라이딩 윈도우와 비슷하긴 하다.

입력받은 선들을 시작점을 기준으로 정렬해보자. 우리는 선의 총 길이를 구해야 하기 때문에 제일 왼쪽의 선부터 하나씩 읽어가면서 전체 선이 어떻게 만들어지는지 관찰하면 된다.

정렬된 선 2개가 있다고 가정하자. 왼쪽의 선을 A, 오른쪽의 선을 B라 하자. 둘의 관계에는 어떤 경우가 있을 수 있을까?

1. A와 B가 일부분 겹칠 때
   이때는 B의 끝점이 A의 끝점보다 멀리있을 때이다. 두 선은 합쳐지면서 시작점은 유지되지만 끝점은 연장된다.
2. B가 A에게 완전히 포함될 때
   이때는 A의 끝점이 B의 끝점보다 멀기 때문에 두 선은 합쳐지지만 길이는 A가 된다.
3. A와 B의 겹치는 부분이 없을 때
   이때는 독립적인 두 선이 된다.

위 3 경우는 모두 두 선의 위치 관계로 파악할 수 있다. 각 경우에 대하여 분기처리하여 구할 수 있다.

풀이

        int ans = 0;
        int start = lines[0].x;
        int end = lines[0].y;
        for(int i=1;i<N;i++){
            int x = lines[i].x;
            int y = lines[i].y;

            if(x <= end){
                if(y <= end){
                    continue;
                } else{
                    end = y;
                }
            } else{
                ans += (end - start);
                start = x;
                end = y;
            }
        }

정렬된 lines 배열을 하나씩 읽으면서 분기처리한 코드이다.
독립적인 선이 생길 때마다 정답에 길이를 누적해주고 기준 선을 갱신하였다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class App {
    static int N;
    static xy[] lines;
    static class xy implements Comparable<xy> {
        int x;
        int y;
        public xy(int x, int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public int compareTo(xy o) {
            return this.x - o.x;
        }
        
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        lines = new xy[N];
        for(int i=0;i<N;i++){
            String[] s = br.readLine().split(" ");
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);

            lines[i] = new xy(x, y);
        }

        Arrays.sort(lines);

        int ans = 0;
        int start = lines[0].x;
        int end = lines[0].y;
        for(int i=1;i<N;i++){
            int x = lines[i].x;
            int y = lines[i].y;

            if(x <= end){
                if(y <= end){
                    continue;
                } else{
                    end = y;
                }
            } else{
                ans += (end - start);
                start = x;
                end = y;
            }
        }

        ans += (end - start);
        System.out.println(ans);
    }
}