9-7: 구간의 합집합
구간의 합집합 (union.cpp)
문제
구간은 [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]를 출력한다.
예제 입력
2
1 4
3 5
3예제 출력
3예제 입력
3
1 3
2 10
1 8
5예제 출력
3
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class union {
/**
*
* 문제: 구간은 [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]를 출력한다.
*
*
* 예제 입력:
*
* 2
* 1 4
* 3 5
* 3
*
*
* 예제 출력:
* 3
*
* @param args
*/
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
long bounds[][] = new long[N][2];
long max = 0, min = Long.MAX_VALUE;
for (int i=0; i<N; i++){
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
bounds[i][0] = Long.parseLong(st.nextToken());
bounds[i][1] = Long.parseLong(st.nextToken());
if (max < bounds[i][1]){
max = bounds[i][1];
}
if (min > bounds[i][0]){
min = bounds[i][0];
}
}
long i = Long.parseLong(br.readLine());
if (debug) System.out.println("targetIndex: " + i);
long result = binarySearch(min, max, bounds, i);
System.out.print(result);
}
// private static boolean debug = true;
private static boolean debug = false;
private static long binarySearch(long start, long end, long[][] bounds, long targetIndex){
while (start <= end){
if (debug) System.out.println("\nstart: " + start+ ", end: " + end);
long mid = (start + end) /2;
//assume mid is target number
if (debug) System.out.println("mid: " + mid);
//for each bound, check if bound contains mid. compute index from start.
//find index range for element mid.
long index = 0;
long midContainCount = 0;
for (int i=0; i<bounds.length; i++){
long upper= bounds[i][1];
long lower = bounds[i][0];
if (debug) System.out.println("bound's lower: " + lower+ ", upper: " + upper);
if (mid <= upper && mid>= lower){
if (debug) System.out.println("element " + mid +" is between lower and upper, add index by " + (mid - lower));
index+= mid - lower;
midContainCount++;
} else if (mid > upper){
if (debug) System.out.println("element " + mid +" is beyond lower and upper, add index by " + (upper-lower+1));
index+=upper-lower+1;
}
}
if (debug) {
System.out.println("index: " + index);
System.out.println("midContainCount: " + midContainCount);
System.out.println("index range: " + index + "~ " + (index + midContainCount-1));
}
if (targetIndex==index){
if (debug) {
System.out.println("target index equals index");
}
if (midContainCount !=0) return mid;
start = mid+1;
} else if (targetIndex > index){
if (debug) {
System.out.println("target index greater than index");
}
if (targetIndex <= (index+midContainCount-1) && midContainCount!=0) return mid;
//else mid will have bigger value.
start = mid +1;
} else if (targetIndex < index){
if (debug) {
System.out.println("target index less than index");
}
end = mid - 1;
}
}
return 0;
}
}