3일차 문제는 백준 11663번 '선분 위의 점'이다.
https://www.acmicpc.net/problem/11663
이번 문제도 '이분 탐색' 알고리즘으로 해결하는 문제였다.
어제 문제보다 확실히 간단해보여서 부담감이 덜했다.
초기 문제 해결 아이디어는 아래와 같았다.
- N개의 점 좌표를 저장한 배열 arr1을 정렬한다.
- M개의 선분들을 arr2에 저장한다.
- 각 선분의 시작값을 x, 끝값을 y로 입력받고,
- y보다 큰 수 앞에 멈추고 x까지 좁혀가며 개수를 계산한다.
그리고 이번에도 1 ≤ N, M ≤ 100,000 이었기 때문에
nlogn으로 풀어야 해서 이중 for문 이상은 사용하면 안되는 문제였다.
이렇게 구현하려고 '이분 탐색'에 대해 찾아보다가
lowerBound와 upperBound로 문제를 해결하면 보다 간단하게 구현할 수 있을 것 같았다.
lowerBound와 upperBound
lowerBound는 특정 값의 시작 위치를, upperBound는 특정 값보다 처음으로 큰 값의 위치를 찾는 알고리즘이다.
만약 내가 x와 y를 입력받고
y 초과의 수 중 첫 번째 인덱스 값에서 x 이상의 수 중 첫 번째 인덱스 값을 빼면
x와 y 사이에 위치하는 점의 개수를 구할 수 있는 것이다.
예를 들어,
점들의 배열: [1, 3, 10, 20, 30]
선분: [3,15]
이 경우에
lowerBound(3)
start = 0, end = 5 (배열 크기)
mid = (start + end) / 2 = 2 (arr[2] = 10)
-> 10≥3 : end = mid
mid = (0 + 2) / 2 = 1 (arr[1] = 3)
-> 3≥3: end = mid
mid = (0 + 1) / 2 = 0 (arr[0] = 1)
-> 1<31 : start = mid + 1
결과: start = 1 (인덱스 1)
그리고 upperBound(15)
start = 0, end = 5
mid = (0 + 5) / 2 = 2 (arr[2] = 10)
-> 10≤15: start = mid + 1
mid = (3 + 5) / 2 = 4 (arr[4] = 30)
-> 30>15: end = mid
mid = (3 + 4) / 2 = 3 (arr[3] = 20)
-> 20>15: end = mid
결과: start = 3 (인덱스 3)
최종적으로
upperBound(15) - lowerBound(3) = 3 - 1 = 2
이렇게 된다면, 원하는 결과가 나온다.
이를 구현한 코드는 다음과 같다.
package Boj;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Boj11663 {
static int N, M;
static int[] arr1, arr2;
static int result, x, y = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr1 = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr1[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr1);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
result = upperBound(arr1, y) - lowerBound(arr1, x);
sb.append(result).append("\n");
}
System.out.println(sb.toString());
}
static int lowerBound(int[] arr, int x) {
int start = 0, end = arr.length;
while (start < end) {
int mid = (start + end) / 2;
if (arr[mid] < x) {
start = mid + 1;
} else {
end = mid;
}
}
return start;
}
static int upperBound(int[] arr, int y) {
int start = 0, end = arr.length;
while (start < end) {
int mid = (start + end) / 2;
if (arr[mid] <= y) {
start = mid + 1;
} else {
end = mid;
}
}
return start;
}
}
여기서 시간복잡도는 다음과 같았다.
- 점 배열 정렬은 O(NlogN)
- lowerBound와 upperBound는 각각 이분 탐색으로, 배열의 크기 N에 대해 O(log N)
- 이를 M번 반복하므로, O(MlogN)
- 최종적으로 O((N+M)logN)이다.
오늘의 문제 해결
1. lowerBound, upperBound 개념을 학습한 후에 이를 판단하는 기준을 세우는 데 시간이 걸렸다.
-> lowerBound는 x값 (선분 시작값) 이상의 첫 번째 인덱스를 반환하도록 했다.
-> upperBound는 y값 (선분 끝값) 초과의 첫 번째 인덱스를 반환하도록 했다.
2. 컴파일 에러가 발생했다.
-> 살펴보니 StringTokenizer로 x와 y를 입력하면 되는 것을 이중 for문으로 선분 값을 받도록 했던 것이다.
-> 이중 for문을 제거하고, x와 y에 st.nextToken()을 이용해서 값을 넣었다.
3. 출력값이 올바르지 않았다.
-> System.out.println(sb.toString())를 for문 안에 넣어버리는 어이없는 실수를 했었다.
-> 그 밖에 위치하도록 수정했더니, 결과값이 올바르게 출력됐다.
오늘의 회고
1시간 권장이었던 문제를 1시간 30분이 걸렸다.
이번 문제는 이분 탐색의 개념을
제대로 익히고 구현해볼 수 있었다.
이제 이분 탐색, 매개 변수 탐색 등을 문제마다
명확히 어떤 알고리즘을 적용해야 할 지
판단하는 역량을 길러야 할 것 같다.
그리고.. 실수를 줄여야 한다!
lowerBound와 upperBound는 java.util.Arrays 패키지를 사용해서 간단하게 구현할 수 있다는 것도 알게 되었다.
static int lowerBound(int[] arr, int x) {
int pos = Arrays.binarySearch(arr, x);
return (pos < 0) ? -(pos + 1) : pos;
}
static int upperBound(int[] arr, int y) {
int pos = Arrays.binarySearch(arr, y + 1);
return (pos < 0) ? -(pos + 1) : pos;
}
하지만 현재 내 수준에서는 직접 구현하는 것이 우선일 것 같아서,
또 이러한 유형을 만났을 때 이 방법으로 구현하는 것을 연습해 봐야겠다.