[BOJ/백준] 2170 선 긋기 (G5)

문제

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

 

풀이

선의 정보를 입력받은 후 계산을 순차적으로 하기 위해 선의 시작 지점을 기준으로 오름차순 정렬하였으며 시작 지점이 같은 경우에는 끝 지점을 기준으로 오름차순 정렬하였다. 

 

처음에 이전 선의 정보를 start에 시작 지점을 저장하고 end에 선의 끝 부분을 저장했다. 그리고 end - start로 현재까지의 선의 길이를 저장했다. 

이제 이후의 선들을 비교할 때마다 3가지 조건에 맞게 계산을 해줘야 한다.

1. 현재 선이 이전 선에 겹치는 경우(현재 선이 이전 선에 포함되는 경우) → continue로 넘어간다.
2. 현재 선의 시작 지점이 이전 선에 겹치는(포함되는) 경우 → 현재 선의 끝 지점 - 이전 선의 끝 지점(end)를 length에 더해준다.
3. 현재 선이 이전 선과 겹치지 않는 경우 → 현재 선의 끝 지점 - 현재 선의 시작 지점을 length에 더해준다.

그리고 매 조건이 끝날 때마다 다음 루프를 위해 현재 선의 정보를 start와 end에 저장해야 한다.

Code

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

public class BOJ_2170 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int arr[][] = new int [N][2];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

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

        int start = arr[0][0];
        int end = arr[0][1];
        int length = end - start;
        for (int i = 1; i < N; i++) {
            if (start <= arr[i][0] && end >= arr[i][1]) {  // 선이 완전히 겹치는 경우(포함된 경우)
                continue;
            } else if (arr[i][0] < end) {  // 현재 선의 시작 부분이 이전 선에 포함된다면
                length += arr[i][1] - end;  // 길이에 증가된 길이만큼 추가
            } else {  // 현재 선 밖으로 나간 경우(겹치지 않는 경우)
                length += arr[i][1] - arr[i][0];
            }
            start = arr[i][0];  // 다음 루프에서 비교될 현재 선을 짖정
            end = arr[i][1];
        }

        bw.write(length + "");
        bw.flush();
        bw.close();
    }
}