백준 2170 자바 - 선 긋기 (boj 2170 java)

문제 : boj2170

 

  당연히 전체 위치를 보게되면 -10억부터 +10억까지 봐야하므로 시간초과가 뜬다. 최대 100만개인 N을 기준으로 동작할 방법을 찾아야 한다.

 

  문제에서 제시된 '예제 입력 1'은 이미 그렇게 정렬된 데이터긴 하지만, N개를 전부 x를 기준으로 오름차순으로 정렬했다고 생각하고 어떻게 풀지 한번 생각해보자.

4
1 3
2 5
3 5
6 7

 

  그렇다면 위와 같이 x값 기준 오름차순으로 차례대로 확인할 경우(x값이 동일할 경우 y값 순서는 상관 없음. 그나마 내림차순으로 하면 아주 약간의 대입연산 정도는 줄여볼 수 있는데 의미 없음), 이전 y 값보다 현재의 x값이 작거나 같다면 이어진 항목으로 생각해볼 수 있다. 1-3을 본 후, 2-5를 보자. 현재 보고 있는 x인 2는 이전의 y값인 3보다 작으므로 겹치는 구간이야 어떻든, 그냥 이어져 있다고 볼 수 있다. 따라서 구간을 [이전 x값 ~ 현재 y값과 이전 y값 중 큰 값] 으로 변경해도 문제가 없을 것이다.

 

  그리고 3-5도 마찬가지로 포함된다. 그 다음 6-7을 보면 이전 y값인 5보다 현재의 x값인 6이 더 크므로 서로 다른 구간이라 볼 수 있다. 그럼 이제 이전의 구간인 1-5는 필요가 없으므로, 별도의 변수에(코드에선 sum) 이전 구간의 길이를 넣어주고(=4), 새로운 구간인 6-7을 진행한다. 만약 그 뒤에 7-10 이라는 구간도 있었다면 이제 6-10으로 구간이 확장되게 될 것이다. 이런식으로 반복을 해주면 된다. 그럼 N개에 대해 정렬 O(NlogN)에, N개의 구간을 순차적으로 확인하면 되므로(O(N)), 최종적으로 O(NlogN+N) = O(NlogN) 정도에 문제를 풀 수 있다.

 

  다 입력받은 후 정렬해도 되지만, 내 경우엔 PriorityQueue를 사용해서 진행했다(이런 경우에 좀 더 빠름. 어차피 둘 다통과 가능하므로 별 의미는 없음).

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    class Line implements Comparable<Line> {
        int x, y;
        public Line(int x, int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public int compareTo(Line o) {
            if (this.x == o.x) return o.y-this.y;
            return this.x-o.x;
        }
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Line> pq = new PriorityQueue<>();
        while(n-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            pq.add(new Line(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        int sum = 0;
        int bfX = pq.peek().x;
        int bfY = pq.peek().y;
        pq.poll();
        while (!pq.isEmpty()) {
            Line cur = pq.poll();
            if (cur.x > bfY) {
                sum += bfY-bfX;
                bfX = cur.x;
                bfY = cur.y;
                continue;
            }
            bfY = Math.max(bfY, cur.y);
        }
        System.out.println(sum+bfY-bfX);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}