취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14170번 문제인 Counting Haybales이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/14170 

구간 [L,R]에 존재하는 haybale의 수는 R 이하의 위치에 존재하는 haybale의 수에서 L 미만의 위치에 존재하는 haybale의 수를 빼는 것으로 계산할 수 있음을 관찰하자. 따라서 x 미만 위치, 그리고 x 이하 위치에 존재하는 haybale의 수를 빠르게 구할 수 있다면 문제를 해결할 수 있다.

주어진 haybale들의 위치를 배열에 크기순으로 정렬해 저장하자. 이 때, x보다 작은 수 중 가장 큰 수의 인덱스와 x보다 큰 수중 가장 작은 수의 인덱스는 이진탐색(binary search)를 통해 구해낼 수 있다. 이 인덱스를 이용하면 위의 계산에 필요한 값을 계산할 수 있다는 점을 관찰해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using namespace std;

int N, Q;
int arr[100002];

int func1(int val) {
	int L = 0, R = N + 1;
	while (L < R) {
		int mid = (L + R) / 2 + 1;
		if (arr[mid] < val) L = mid;
		else R = mid - 1;
	}

	return L;
}

int func2(int val) {
	int L = 0, R = N + 1;
	while (L < R) {
		int mid = (L + R) / 2;
		if (arr[mid] > val) R = mid;
		else L = mid + 1;
	}

	return L;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> Q;
	for (int i = 1; i <= N; i++) cin >> arr[i];
	arr[0] = -1, arr[N + 1] = 1000000007;

	sort(arr, arr + N + 2);

	while (Q--) {
		int qL, qR; cin >> qL >> qR;
		int L = func1(qL), R = func2(qR);

		cout << R - L - 1 << '\n';
	}
}