2170번 : 선 긋기

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

2170번: 선 긋기

 

문제

매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

 

입력

첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

 

출력

첫째 줄에 그은 선의 총 길이를 출력한다.

 

---

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int arr[][] = new int[n][2];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        // sorting
        Arrays.sort(arr, new Comparator<int[]> () {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                } else return o1[0] - o2[0];
            }
        });

        long result = 0;
        int s = arr[0][0]; // 기존 선 시작점
        int e = arr[0][1]; // 기존 선 끝점
        for (int i = 1; i < n; i++) {
            int ns = arr[i][0]; // 현재 선 시작점
            int ne = arr[i][1]; // 현재 선 끝점
            
            // 연장
            if(s <= ns && ns <= e) {
                if(e < ne) e = ne;
            }
            // 포함
            else if(s <= ns && ne <= e) {
                continue;
            }
            // 새로운 선
            else {
                result += (Math.abs(e - s)); // 기존 선 길이 계산
                s = ns;
                e = ne;
            }
        }

        result += (Math.abs(e - s)); // 마지막 선 길이 계산
        System.out.println(result);
    }
}

 

해결방법

정렬 + 스위핑 알고리즘을 사용하여 문제를 해결했다.

문제는 의외로 간단하다. 먼저 시작점과 끝점 기준으로 정렬을 해준다. 그러면 시작점이 가장 작은 선부터 순서대로 배열에 정렬된다.

 

배열에 저장된 모든 선을 탐색하면서 아래 세 가지 경우만 판단하면 된다.

1) 선분이 새로 시작되는 경우

2) 선분이 연장되는 경우

3) 선분이 기존에 그렸던 선분에 완전히 포함되는 경우

 

세 가지 경우를 판단하여 코드를 구현하면 쉽게 해결할 수 있다.