백준 8807 자바 - Przedziały (BOJ 8807 JAVA)

문제 : boj8807

 

 

1. 다음과 같은 입력을 생각해보자.

1
5
1 2
2 2
3 5
7 8
10 10

  이 문제의 경우 만약 모든 범위를 한 선에 겹쳐그릴 수 있다면 쉽게 답을 구할 수 있을 것이다.

  그럼 어떻게 각 범위를 합칠 수 있을지 생각해보면 된다. 우선 가장 간단한 방식으로, 모든 범위에 해당하는 배열을 만들고 입력을 받으며 범위를 채운 후, 마지막에 모든 범위에 대해 확인해서 개수를 세는걸 생각할 수 있다. 다만 이 문제의 경우 이렇게되면 모든 범위가 -10억~+10억이 되므로 모든 범위 확인만해도 대략 20초정도 걸린다. 

 

 

2. 다른 방법을 생각해보자.

  사실 각 A,B에 대해 범위를 순회만 해도 최대 20억번 해야하므로 시간초과가 확실하다. 따라서 아예 다른 방식으로 생각해봐야 한다.

 

  ORDER BY A ASC, B ASC로 정렬을 한다고 해보자(A가 동일하다면 B 오름차순, 아니라면 A 오름차순). 그리고 정렬된 순서대로 보면서 매번 이전까지 나온 B의 최대값과, 현재 보고 있는 범위의 A를 비교해보면 어떨까? 현재까지 나온 B보다 A값이 2이상 크다면 이전까지 나온 구간과 다른 떨어진 구간인 것이 된다.

 

  위의 이미지를 다시 보자.

 

  A=1, B=2를 본 후, (2,2)를 본 경우 현재 마지막 B는 2이므로 (2,2)는 의미가 없다. 그 다음 (3,5)는 3이 2보다 1만 크므로 연속된 구간이라 볼 수 있다. 따라서 최종 B만 5로 증가시킨다. 그리고 (7,8)을 보니 7이 5와 2이상 차이난다. A를 기준으로 정렬해뒀으므로 그 이후의 모든 값들은 A가 7이상이다. 따라서 이전까지 나왔던 구간 (1,5)에서 나올 수 있는 정수의 개수를 따로 CNT에 더해두고 이제 그 구간은 신경을 안써도 된다. 새로운 구간 (7,8)만 보면 된다. 다음으로 (10,11)도 10과 8이 2이상 차이나므로 새로운 구간이므로 (7,8)에서 나올 수 있는 정수를 또 CNT에 더해두고 (10,11)만 신경쓰면 된다.

 

  위 과정을 통해 유효한 시간내에 통과할 수 있다.

 

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.Arrays;

class Range implements Comparable<Range> {
    int a, b;
    public Range(int a, int b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public int compareTo(Range o) {
        if (this.a == o.a) return this.b - o.b;
        return this.a - o.a;
    }
}

public class Main extends FastInput {
    private void solution() throws Exception {
        int z = nextInt();
        StringBuilder sb = new StringBuilder();

        while (z-->0) {
            int n = nextInt();
            Range[] arr = new Range[n];
            while (n-->0) {
                arr[n] = new Range(nextInt(), nextInt());
            }
            Arrays.sort(arr);

            int s = arr[0].a;
            int e = arr[0].b;
            int cnt = 0;
            for (int i = 1; i < arr.length; i++) {
                if (arr[i].a > e+1) {
                    cnt += e-s+1;
                    s = arr[i].a;
                }
                e = Math.max(e, arr[i].b);
            }
            cnt += e-s+1;

            sb.append(cnt).append('\n');
        }
        System.out.print(sb);
    }

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

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        boolean neg = (c == '-');
        if (neg) c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        if (neg) return -ret;
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}