공항

Problem link: https://www.acmicpc.net/problem/10775

이진 트리(i.e. std::set)을 활용해서 풀어주었다.

쉽게 풀고나서 혹시나 하는 마음에 문제 분류를 보니 Disjoint Set을 활용해서도 풀어줄 수 있는 모양이다.

시간복잡도 측면서에 내 풀이와 별반 다르지 않다는 생각이 들어서 다시 풀지는 않았다.

내 아이디어는 아래와 같다.

• 1번 게이트, 2번 게이트 ..., G번 게이트를 내림차순으로 std::set에 저장한다.
• 1 ~ g_i게이트에 도킹을 희망하는 비행기의 도킹 게이트는 위의 std::set에서 lower_bound로 찾아준다(역시 내림차순).
• 도킹을 못하면 더 이상 도킹 불가이니 그만 두고 답을 출력한다.
• 도킹을 할 수 있다면, lower_bound를 std::set에서 삭제해준다.

#include <set>
#include <cstdio>

using namespace std;

int G;
int P;
int PLANES[100000];

int main(void)
{
  scanf(" %d", &G);
  set<int> gates;
  for (int g = 1; g <= G; ++g)
  {
    gates.insert(-g);
  }

  scanf(" %d", &P);
  for (int it = 0; it < P; ++it)
  {
    scanf(" %d", &PLANES[it]);
  }

  int answer;
  for (answer = 0; answer < P; ++answer)
  {
    auto it = gates.lower_bound(-PLANES[answer]);
    if (it == gates.end())
    {
      break;
    }
    else
    {
      gates.erase(it);
    }
  }

  printf("%d\n", answer);

  return 0;
}