백준 15922 자바 - 아우으 우아으이야!! (BOJ 15922 JAVA)

문제 : boj15922

 

  결국 겹치는 구간은 무시하고, 모두 그려봤을 때 실제 포함되는 구간만을 구하면 된다. 이에 따라 예제 입력 1은 다음과 같이 생각해볼 수 있다.

 

  그렇다고 배열같은거에 기입하자니 20억개나 표현이 가능해야하고, 당연히 이건 단순 순회만으로도 시간초과가 나게 된다.

  따라서 내 경우엔 우선 각 x값을 기준으로 정렬한 후 현재 측정중인 구간의 시작 x와 끝점 y를 따로 기록해뒀다(코드에서 s와 e). 로직은 다음과 같다.

 

A. x값을 기준으로 오름차순으로 정렬된 데이터를 차례대로 확인한다. 첫 s와 e는 즉 가장 x가 낮은 데이터 중 하나의 값과 동일해진다.

 

B. 이후 각 (x,y)를 순회하면서 x가 e 이하라면 이전까지 보고 있던 (x,y)와 같은 구간으로 칠 수 있으므로 e만 조정한다(e와 y중 큰 값으로).

 

C. 'B'에서 x가 e보다 크다면 새로운 구간이므로, 이전까지 보고 있던 구간의 길이를 답변 길이에 더해주고 (answer+=e-s), s와 e를 새로 갱신한다.

 

위의 과정을 반복하면 답을 구할 수 있다. 예제 입력 1에 대해 위의 과정을 그림으로 그려보면 다음과 같다.

 

 

코드 : github

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

class Pos implements Comparable<Pos> {
    int x, y;
    public Pos(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Pos o) {
        if (this.x == o.x) return this.y - o.y;
        return this.x - o.x;
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        ArrayList<Pos> arr = new ArrayList<>();
        while (n-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr.add(new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        Collections.sort(arr);

        int s = arr.get(0).x;
        int e = arr.get(0).y;
        int answer = 0;
        for (int i = 1; i < arr.size(); i++) {
            Pos cur = arr.get(i);
            if (e >= cur.x) {
                e = Math.max(e, cur.y);
            } else {
                answer += e-s;
                s = cur.x;
                e = cur.y;
            }
        }
        answer += e-s;

        System.out.println(answer);
    }
}