BOJ 10775: 공항

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

10775번: 공항

요즘 공부를 너무 게을리했기에 간만에 감을 찾고자 BOJ를 켰다. 딱히 눈에 띄는 문제가 없어 단계별로 풀어보기나 차례대로 풀고자 하여 찾은 문제이다.

알고리즘 분류상에는 union-find라고 되어있었기에 약간 응용하면 되겠거니라는 생각에 문제를 풀기 시작했다.

 

가장 먼저 떠올린 방법은 정말 단순하게 union-find를 이용하는 방법이었다.

0번 node에 union된 node들이 도킹된 게이트라고 가정하고 입력받은 $g_i$를 순서대로 도킹시켰다.

하지만 아래와 같은 예제가 들어온다면 조금 다른 방법을 이용하여 도킹시켜야만 했다.

4 6
4
4
4
4
4
4

첫 번째 4를 입력으로 받을 때 0번 node에 union시키고 두 번째 4를 입력으로 받을 때 문제가 생긴다.

이미 4번 node는 union된 상황이기 때문에 다른 게이트를 찾아서 도킹을 시켜야만 하지만 이 게이트를 어떤 방식으로 찾아야 할 지 쉽게 생각하지 못했다.

특정 게이트가 이미 도킹되어 있는지 아닌지를 체크하는 배열을 만들어 해볼까 했지만 $g_i$가 10만으로 계속 들어오는 최악의 경우 TLE를 받겠다는 생각과 함께 방법을 바꾸기로 생각했다.

 

두 번째로 생각한 방법은 위의 방법에서 체크하는 배열을 이분 탐색을 이용해 비어있는 게이트를 찾는 방법이다.

하지만 특정 게이트가 이미 도킹되어 있는 상태라고 가정했을 때 해당 위치의 왼쪽으로 탐색해야 할 지, 오른쪽으로 탐색해야 할 지를 결정할 수 없기 때문에 역시 방법을 바꾸기로 생각했다.

 

이때쯤 떠올린 방법이 세그먼트 트리를 이용하여 해결해보는 것은 어떨까라는 방법이다.

맨 처음에는 단순히 $g_i$를 입력받을 때마다 $[1, g_i]$ 구간에 query를 보내고 이 값이 $g_i$보다 크면 도킹을 멈추고 작다면 $g_i$를 1 증가시켜주는 방식을 생각해봤지만 아래와 같은 케이스의 경우 정확한 답을 낼 수 없었다.

3 4
3
3
3
1

3번 게이트에 이미 3대의 비행기가 도킹을 시도했기 때문에 1, 2, 3번 게이트 모두 도킹된 상황이지만 마지막 1을 입력으로 받으면 1보다 큰 위치에 도킹되었는지 아닌지를 확인할 수 없기에 그대로 도킹해버렸고 잘못된 답을 내놓는 상황이 된다.

 

그래서 다시 생각해본 방법이 지금까지 들어온 $g_i$중 최댓값을 보관하는 $M$이라는 변수를 만들고 $[1, M]$ 구간에 query를 보내는 방식이다. 이 값이 $g_i$보다 크면 도킹을 멈추고 작다면 $g_i$를 1 증가시켜주는 방식으로 답을 구해봤다. 하지만 아래와 같은 케이스의 경우 정확한 답을 낼 수 없었다.

4 4
3
4
3
3

맨 마지막 3이 입력으로 들어왔을 때 1번 게이트가 비어있는 상황이지만 항상 $[1, M]$ 구간을 확인하며 $g_i$보다 큰지 아닌지를 비교하기 때문에 답을 구할 수 없었다. 따라서 도킹 위치를 정확하게 표시하지 않는 방법은 답을 구하기 어렵겠다는 생각을 하고 방법을 약간 바꿔보기로 하였다.

 

다음으로 생각해낸 방법은 세그먼트 트리의 update 부분을 약간 변형시키는 것이다. 특정 위치의 값을 1 증가시키는 update를 적절한 위치로 찾아가게끔 바꾸어보려고 했지만 오랫동안 문제를 안풀어 구현능력이 많이 떨어진 탓인지 생각대로 구현이 되질 않았기에 다른 방법을 떠올리기로 하였다.

---

마지막으로 생각한 방법은 set을 이용하는 방법이다.

set에 1부터 $g$까지의 값을 미리 insert해둔 후, 입력받은 $g_i$를 기준으로 lower_bound를 찾은 뒤 해당 수보다 작거나 같은 가장 큰 값을 찾아 해당 값을 erase 해주는 방식을 이용했다.

방법을 조금 자세히 설명하자면 먼저 $lower\_bound(g_i) = it$라고 했을 때, $it$가 가리키는 값이 $g_i$인 경우에는 해당 게이트에 아직 도킹이 아직 되지 않았으므로 도킹을 해주면 된다. 큰 경우에는 이미 해당 게이트에 도킹이 되어있는 상태이므로 해당 게이트 번호보다 낮은 위치를 찾아야만 한다. 이를 찾기위해 $it$를 1 감소시켜주는 방법을 이용했다.

여기서 주의해야 할 점은 $it$가 가리키는 위치가 begin() 또는 end()인 경우와 set이 비어있는 경우(사실 앞의 조건에 포함되긴 하지만)이다.

만약 $it$가 가리키는 위치가 begin()이라면 $it$를 1 감소시켜주는 연산을 할 수 없다. 만약 연산을 하게 된다면 segment fault 오류를 받게 된다. 이와 달리 $it$가 가리키는 위치가 end()인 경우에는 $it$가 가리키는 값을 확인할 경우 segment fault 오류를 받을 수 있다. 따라서 begin()을 가리키고 있는 경우 해당 위치의 값과 비교하여 $g_i$보다 크다면 확인을 멈추고, end()를 가리키고 있는 경우에는 set이 비어있지 않은 경우에만 $it$를 1 감소시켜 값을 가리키는 위치로 이동할 수 있게 만들어 줘야만 한다.

 

AC를 받은 코드는 아래에서 확인할 수 있다.

#include<bits/stdc++.h>
using namespace std;
int main(){
  int g, p; scanf("%d %d", &g, &p);
  set<int> s;
  for(int i = 0; i<g; ++i)
    s.insert(i + 1);
  int ans = 0;

  for(int i = 0; i<p; ++i){
    if(s.empty()) break;
    int num; scanf("%d", &num);
    auto it = s.lower_bound(num);
    if(it == s.end()) --it;
    if(it != s.end() && *it > num){
      if(it == s.begin()) break;
      --it;
    }
    s.erase(it);
    ++ans;
  }
  printf("%d\n", ans);
}

 

union-find를 이용한 풀이는 천천히 고민해봐야겠다.