[BOJ] 2170 선 긋기 (Java)

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

 

<알고리즘>

처음엔 pq를 사용했는데 시간초과가 떠서 방법을 변경했다.

정렬 후에는 이후 값이 무조건 직전값에 영향을 받을 수 밖에 없기에 그때그때 확장하는 방법이 가능해진다.

 

1. x값 오름차순 정렬 x값이 같다면, y값 오름차순 정렬

2. 만약 다음 값이 이전 값에 걸친다면 끝 좌표만 확장

2. 만약 걸치지 않는다면 이전 선의 길이를 계산해 저장한 후, 현재 x, y를 새로운 시작과 끝 값으로 정의

3. 마지막 선 길이까지 더한 후 결과 출력

 

<제출코드>

package BOJ.Greedy;

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

public class BOJ_2170_선긋기 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);


        int s = arr[0][0];
        int e = arr[0][1];
        int ans = 0;
        for(int i=1; i<n; i++) {
            // 1. 선이 겹치는 경우
            if(arr[i][0] <= e){
                e = Math.max(e, arr[i][1]);
            }
            // 2. 선이 겹치지 않는 경우
            else{
                ans += e - s;
                s = arr[i][0];
                e = arr[i][1];
            }
        }
        ans += e - s;
        System.out.println(ans);
    }
}