[백준 - 2024번] 선분 덮기 - Java

문제 링크

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

문제

티어: 골드 3
알고리즘: 그리디, 정렬

X축 위에 여러 개의 짧은 선들이 흩어져 있다. 이 선들은 [Li, Ri]로 나타내는데 이는 선이 Li에서 시작해 Ri에서 끝남을 의미한다. 우리는 이들 중 적은 수의 선들만을 이용해서 [0, M]을 완전히 덮어 버리고 싶다. 최소 개수의 선들을 이용하여 [0, M]을 덮어버리는 프로그램을 작성하시오.

입력

각 테스트 케이스는 M(1 ≤ M ≤ 50,000) 과 "Li Ri"(|Li|, |Ri| ≤ 50,000, i ≤ 100,000)쌍으로 구성이 된다. 각각은 다른 행으로 분리되어 있다. 입력은 "0 0"으로 끝난다. 모든 입력은 정수이다.

출력

[0, M]을 덮는데 필요한 선의 개수를 출력한다. 만약 선을 덮는 방법이 존재하지 않으면 “0”을 출력하면 된다.

풀이

목표는 최소 개수의 선들을 이용하여 [0, M]을 덮는 것이다.

그러면 0,M 구간을 최대한 많이 덮는 선을 이용하면 될 것 같다는 생각이 든다.

그러니까 -1 5, 와 -3 6중 더 우선 순위가 높은 선은 -2 6이다.

여기서 만약 2 10 선이 같이 비교된다면 이 선이 가장 우선 순위가 높다고 할 수 있을까?

우리가 덮어야 하는 구간은 0 ~ M이기 때문에 0 2 구간을 포함하면서 R이 가장 큰 선을 구하는 것이 핵심이다.

그러니까 초기에는 0을 포함하면서 R이 가장 큰 선을 구하고, 이후 또 덮어야 지점을 업데이트해서 M까지 덮는다면 최소 개수의 선들로 덮을 수 있다.

그래서 일반화 하자면,

어떤 지점 L에서 그 지점과 같거나 작은 지점에서 시작하는 선분 중에서 우선 순위는 R이 가장 큰 선이다.

먼저, L을 기준으로 오름차순 정렬하고

L = 0, lastR = 0으로 초기화 해준다.

그리고 순차 탐색을 하는데

L보다 같거나 작은 경우 && lastR보다 큰 경우에 lastR을 업데이트 해준다.

그리고 L을 벗어나는 경우에 덮어야 하는 구간은 lastR로 업데이트 해준다. 그리고 반복하면 된다.

이때 L을 벗어나는 경우에 lastR이 업데이트 되었는지 체크해야 한다. (업데이트 되지 않았다면, 그 구간에 선이 존재하지 않음을 의미한다.)

시간 복잡도는 O(N)다.

소스 코드

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

class Line implements Comparable<Line> {
    int L, R;
    Line(int L, int R) {
        this.L = L;
        this.R = R;
    }
    
    @Override
    public int compareTo(Line o) {
        if(this.L < o.L) {
            return -1;
        } else if(this.L > o.L) {
            return 1;
        } else {
            if(this.R < o.R) {
                return 1;
            } else if(this.R > o.R) {
                return -1;
            }
        }
        return 0;
    }
    
}

public class Main {
    static int M;
    static ArrayList<Line> list = new ArrayList<>();
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        M = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Line input = new Line(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        while(input.L != 0 || input.R != 0) {
            if(input.R > 0) {
                int L = input.L < 0 ? 0 : input.L;
                list.add(new Line(L, input.R));
            }
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            input = new Line(Integer.parseInt(st2.nextToken()), Integer.parseInt(st2.nextToken()));
        }
        
        Collections.sort(list);
        System.out.println(answer());
    }
    
    static int answer() {
        int cnt = 0;
        int L = 0;
        int lastR = 0;
        int i = 0;
        while(i < list.size()) {
            if(list.get(i).L <= L && list.get(i).R > lastR) {
                lastR = list.get(i).R;
            } 
            
            if(list.get(i).L > L) {
                //업데이트 되었는지 확인
                if(L == lastR) {
                    return 0;
                }
                cnt += 1;
                L = lastR;
            } else {
                i+=1;
            }
            
            if(lastR >= M) {
                cnt += 1;
                return cnt;
            }
        }
        return 0;
    }
}