[백준/C++] 11663번 선분 위의 점

11663번: 선분 위의 점

풀이

선분의 범위 내에 주어진 점이 몇 개 있는지 구하는 문제이다. 순차 탐색으로는 구현하기 쉬운 문제이지만 좌표의 범위가 넓어 이분 탐색을 통해 탐색 시간을 줄여야 했다.

선분 위에 위치한 주어진 점의 개수 = 주어진 점의 개수 - 선분 위에 위치하지 않는 점의 개수

선분 위에 위치하지 않는 점의 개수 = 선분 시작점보다 좌표의 크기가 작은 점의 개수 + 선분 끝점보다 좌표의 크기가 큰 점의 개수

• 이분탐색 1 : 시작점보다 작은 범위에 있는 점 중에서 최대 좌표의 인덱스 = underIndex
• 이분탐색 2 : 끝점보다 큰 범위에 있는 점 중에서 최소 좌표의 인덱스 = overIndex ⇒ 선분 위의 점의 개수 = overIndex - underIndex
  

---

c++에서 지원하는 이분 탐색 함수를 이용해 문제를 풀 수 있다.

lower_bound(first, last, x) : [first, last) 범위에서 x 이상인 첫 번째 원소의 위치를 반환
upper_bound(first, last, x) : [first, last) 범위에서 x를 초과하는 첫 번째 원소의 위치를 반환

헤더에 들어있으며, 이분 탐색으로 구현되어 있기 때문에 [first, last) 범위 내의 원소들이 오름차순 정렬되어있어야 한다.

반환형은 Iterator 이므로 실제로 몇 번째 인덱스인지 알고 싶다면, 위 코드와 같이 함수 값에서 배열 첫 번째 주소를 가리키는 배열의 이름을 빼 주면 인덱스를 구할 수 있다.

코드

1. 이분 탐색 직접 구현

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int point[100001], n, m;
  cin >> n >> m;

  for (int i = 0; i < n; i++)
    cin >> point[i];

  sort(point, point + n);

  for (int i = 0; i < m; i++)
  {
    int left = 0, right = n - 1, count = 0, underIndex = 0, overIndex = 0;
    int a, b;
    cin >> a >> b;

    while (left <= right)
    {
      int mid = (left + right) / 2;

      if (point[mid] < a)
        left = mid + 1;
      else
        right = mid - 1;
    }

    underIndex = left;
    left = 0, right = n - 1;

    while (left <= right)
    {
      int mid = (left + right) / 2;

      if (point[mid] > b)
        right = mid - 1;
      else
        left = mid + 1;
    }
    overIndex = right + 1;

    count = overIndex - underIndex;
    cout << count << "\n";
  }
  return 0;
}

---

2. 이분 탐색 함수 사용

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int point[100001], n, m, x, y;
  cin >> n >> m;

  for (int i = 0; i < n; i++)
    cin >> point[i];

  sort(point, point + n);
  for (int i = 0; i < m; i++)
  {
    cin >> x >> y;
    cout << upper_bound(point, point + n, y) - lower_bound(point, point + n, x) << "\n";
  }
  return 0;
}