[실전 문제] 구간의 합집합

1. 문제

구간은 [s, e] 로 나타내고, 이 의미는 s, (s+1), (s+2), …, (e-1), e 와 같이 숫자를 나열한 것을 의미한다. 예를 들어, [1, 4]는 1, 2, 3, 4로 숫자를 나열한 것을 의미한다. n개의 구간이 있고, 이 구간들의 숫자를 모두다 새로운 배열 S에 넣어 정렬을 한다. 이 때 S[i] 의 값이 무엇인지 출력하는 프로그램을 작성하시오. 예를 들어, 3개의 구간 [1, 3], [2, 10], [1, 8] 이 있고, S[5]를 알고싶다고 하자. 그러면 S = [1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 10] 이 되고, 따라서 S[5]는 3이 된다. 배열의 인덱스는 0부터 시작한다는 것에 주의하자.

---

입력

첫 번째 줄에 구간의 개수 n이 주어진다 ( 1 ≤ n ≤ 10,000 ) 두 번째 줄부터 각 구간을 나타내는 숫자 s, e가 주어진다. ( 1 ≤ s ≤ e ≤ 1,000,000,000 ) 그 후, 마지막 줄에는 값을 알고 싶은 숫자의 위치 i가 주어진다. ( 1 ≤ i ≤ 10,000,000,000,000 ) i번째 위치에는 항상 숫자가 존재한다고 가정한다. 

출력

S[i]를 출력한다. 

예제 입력

case 1)

2
1 4
3 5
3

 

case 2)

3
1 3
2 10
1 8
5

예제 출력

case 1) 3

case 2) 3

 

 

 

2. 풀이

이 문제는 i 번째 숫자를 찾는 것이 목적이다. 그렇다면 반대로 숫자 P가 몇 번째인가를 생각해보아야한다.

입력	구간
1 3	1   2   3
2 10	2   3   4   5   6   7   8   9   10
1 8	1   2   3   4   5   6   7   8
S	1   1   2   2   2   3   3   3   4   4   5   5   6   6   7   7   8   8   9   10

예를 들어 4가 몇 번째인지 찾는다면, 4보다 작은 갯수를 알면 된다.

1

1

2

2

2

3

3

3

4

4

5

5

6

6

7

...

그렇다면, 입력을 통해 갯수를 안다면,

1 3	1   2   3
2 10	2   3   4   5   6   7   8   9   10
1 8	1   2   3   4   5   6   7   8

• 1   3 구간에서는 3이 4보다 작기 때문에 모든 수는 4보다 작다.
• 2   10 구간에서는 4는 2와 10의 중간이므로 2부터 3
• 1   8 구간에서는 4는 1과 8의 중간이므로 1부터 3
• 즉, 특정 숫자가 몇 번째인지는 O(N)만에 구할 수 있다.

 

그렇다면 이 아이디어를 가지고 3 번째 숫자를 찾는다고 가정해면, 숫자 1이 몇 번째인지(0), 2가 몇 번째인지(2), 3이 몇 번째인지(5)를 알면 3 번째 숫자는 2임을 알 수 있다. 하지만 1부터 시작을 한다면 최대 10억이 몇 번째인지 다 알아야한다. 그렇게 된다면, O(N) x 10억의 시간이 소요된다.

1	1	2	2	2	3	3	3	4	4	5	5	6	6	7	...
0		2	3		5

 

따라서 더 효율적으로 설계해야 문제를 해결할 수 있다. 시간 복잡도를 줄이기 위해서는 이진 탐색을 사용하면 된다.

 

예를 들어 13번째 숫자를 찾고자 할 때, 각각의 숫자가 몇 번째인지를 모두 기록해놓았다고 한다면 쉽게 찾을 수 있다.

1	2	3	4	5	6	7	8	9	10
0	2	5	8	10	12	14	16	18	19

S가 1, E가 10일 때 Mid는 5가 된다.

1 (S)	2	3	4	5 (Mid)	6	7	8	9	10 (E)
0	2	5	8	10	12	14	16	18	19

Mid(5)가 10번째이기 때문에  S를 Mid로 옮길 수 있다. 그 이유는 13번째의 숫자를 알고자 하는데, 5가 10번째 숫자라면 그 전의 숫자는 모두 볼 필요 없기 때문이다.

				5 (S)	6	7 (Mid)	8	9	10 (E)
				10	12	14	16	18	19

Mid(7)이 14번째이기 때문에 E를 Mid로 옮길 수 있다.

				5 (S)	6 (Mid)	7 (E)
				10	12	14

S와 E가 만나게 될 때, 13번째의 숫자를 알 수 있게 된다.

					6 (S)	7 (E)
					12	14

이 과정을 통해 S와 E에 대해 정의를 내려보면 다음과 같다.

• S : 찾고자 하는 숫자보다 더 작거나 같은 숫자 (즉, 찾고자 하는 숫자)
• E : 찾고자 하는 숫자보다 더 높은 숫자

---

위의 경우에는 각각의 숫자가 몇 번째인지를 모두 기록되어 있는 상태이기 때문에 쉽게 알 수 있지만, 기록되어있지 않을 경우에서 정리를 한다면 다음과 같은 과정으로 진행이 된다.

 

- 5(Mid)가 몇 번째인가?

5보다 작은 숫자의 갯수 계산 - O(n)

1 (S)	2	3	4	5 (Mid)	6	7	8	9	10 (E)
				10

- 7(Mid)가 몇 번째인가?

7보다 작은 숫자의 갯수 계산 - O(n)

				5 (S)	6	7 (Mid)	8	9	10 (E)
				10		14

- 6(Mid)가 몇 번째인가?

6보다 작은 숫자의 갯수 계산 - O(n)

				5 (S)	6 (Mid)	7 (E)
				10	12	14

- 13번째 숫자는 무엇인가?

6

					6 (S)	7 (E)
					12	14

총 시간 복잡도는 O(log 10억 x n)이 소요된다.

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int n;
    private static int[] s;
    private static int[] e;
    private static long atIdx;
    private static int res;

    public static void main(String[] args) throws IOException {

        n = Integer.parseInt(br.readLine());

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        s = new int[n];
        e = new int[n];
        StringTokenizer st;
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            s[i] = Integer.parseInt(st.nextToken());
            e[i] = Integer.parseInt(st.nextToken());

            if(min >= s[i]) min = s[i];
            if(max <= e[i]) max = e[i];
        }

        atIdx = Long.parseLong(br.readLine()); // atIdx 번째의 수 찾기

        res = 0;
        binarySearch(min, max);

        bw.write(res + "");
        br.close();
        bw.flush();
        bw.close();
    }

    private static void binarySearch(int start, int end) {
        if(start > end) return;
        else {
            long sum = 0;
            int mid = (start + end) / 2;

            for(int i = 0; i < n; i++) {
                if(e[i] <= mid) {
                    // 구간의 마지막이 전체 수의 중간값보다 작을 경우
                    // 해당 구간의 모든 수는 중간값보다 작기 때문에 해당 구간의 갯수를 더해준다.
                    sum += e[i] - s[i] + 1;
                } else {
                    // 구간의 첫번째가 전체 수의 중간값과 같을 경우
                    // 중간값부터 시작한다는 의미이기 때문에 1을 더해준다.

                    // 구간의 첫번째가 전체 수의 중간값보다 작을 경우
                    // 구간의 첫번째부터 중간값까지의 구간 갯수를 더해준다.
                    if(s[i] == mid) sum += 1;
                    else if(s[i] < mid) sum += mid - s[i] + 1;
                }
            }

            // 찾고자 하는 값의 위치와 전체 수의 중간값의 위치의 비교
            if(sum < atIdx) binarySearch(mid+1, end);
            else if(sum == atIdx) {
                res = mid + 1;
                return;
            } else {
                if(sum > mid) res = mid;
                binarySearch(start, mid-1);
            }
        }
    }

}