풀이#

정말 빡빡하게도, 정석적인 풀이법의 소요시간과 시간초과 기준점이 딱 붙어있게 설계된 문제인 것 같다. 그래서 람다함수에서 병목현상이 일어나 시간초과가 뜬 것 같다. 하지만 람다함수 + 나의 아주 제너럴한 이분탐색 코드를 std::upper_bound 코드로 교체하자 바로 Pass가 떴다. upper_bound 함수는 간단히 주어진 범위 안에서 value <= *it 인지 아닌지만 검사하기 때문에 속도가 빠르다.

어쨌든 기본적인 풀이법은 완전 동일하다.

말의 위치에 대해서만 정렬을 수행한다. (소 ↔ 말 벡터는 사실 뭘 먼저 해도 상관은 없음)
어떤 소 cow에 대해서 말과의 거리를 최소로 하는 말을 찾는다.
그 말과의 거리가 min_dist 보다 작으면 count와 min_dist의 값을 초기화한다.
1. 같으면 count 값을 1 증가시킨다.

2번 과정을 빠르게 수행하는 것이 이 문제의 관건인데, 이를 위해서 이분탐색을 활용한다. 이때 거리를 계산한다고 절댓값을 취해선 절대로 안된다. 참/거짓 구성이 흐트러질 수 있기 때문이다. 그러면 어떻게 하느냐? 이분탐색을 두 번 하는 것에서 아이디어는 출발한다.

소 ≤ 말을 만족하는 첫번째 말을 찾는다.
말 ≤ 소를 만족하는 첫번째 말을 찾는다.

이렇게 두고보니 사실 1번말을 찾으면 자연스럽게 2번말이 튀어나오게 된다. 1번말에 바로 이전 말이 2번말이기 때문!

sol1#

나의 제너럴한 이분탐색 알고리즘이다. T로는 인덱스(숫자)가 와도 되고, STL 처럼 이터레이터가 와도 전혀 무관하다. 핵심은 predicate 안에 있기 때문이다. 함수 이름에서부터 predicate가 true를 만족하는 바로 첫번째 녀석을 이 함수가 찾아주기 때문이다.

/**
F-...-F-F-F-T-T-T-...-T
            ^
*/
template <typename T, class Predicate>
inline T first_true(T begin, T end, Predicate const &pred) {

  T l = begin;
  T r = end;
  while (l < r) {
    T mid = l + (r - l) / 2;
    if (pred(mid)) {
      // next range is [l, mid)
      r = mid;
    } else {
      // next range is [mid + 1, r)
      l = mid + 1;
    }
  }
  return l;
}

아래는 나의 말로 쓴 수도코드를 그대로 c++ 코드로 옮겨적은 모습이다. evaluate 라는 람다함수를 활용하여 코드중복을 해소했다. 왜 두번이나 평가하냐고? 1번말이 첫번째 evaluate이고 2번말이 두번째 evaluate이기 때문.

/**
@return:
 - first: 가장 가까운 쌍의 거리
 - second: 그러한 거리를 갖는 쌍의 개수
*/
inline pair<int, int> solution(vector<int> const &cows, vector<int> &horses) {
  //
  std::sort(horses.begin(), horses.end());

  int min_dist = std::numeric_limits<int>::max();
  int count = 0;

  auto evaluate = [&min_dist, &count](int dist) {
    if (dist < min_dist) {
      min_dist = dist;
      count = 1;
    } else if (dist == min_dist) {
      count += 1;
    }
  };

  for (auto const &cow : cows) {
    // 어떤 소에 대하여 (소 <= 말) 조건을 만족시키는 첫번째 말을 고른다.
    // 그 말의 바로 이전 말과 비교하여 더 가까운 놈을 선택한다.
    auto horse_itr = first_true(horses.begin(), horses.end(),
                                [cow](auto itr) { return cow <= *itr; });
    if (horse_itr != horses.end()) {
      evaluate(abs(cow - *horse_itr));
    }
    if (horse_itr != horses.begin()) {
      evaluate(abs(cow - *(horse_itr - 1)));
    }
  }

  return std::make_pair(min_dist, count);
}

이렇게만 보면 참 깔끔하고 기분이 좋아지는데… 결과는 알다시피 시간초과였다.

sol2#

그래서 무지성으로 horses 벡터를 만들지 않고 메인함수에서 standard input으로 받는 족족 이분탐색을 하면 어떨까 해서 그렇게 해봤지만 마찬가지였다. 결국 나의 이분탐색 코드를 버리고 의미적으로 완전 동일한 upper_bound 함수를 사용하기로 결정했다.

cow를 먼저 입력받으니 얘를 벡터에 넣어 정렬하기로 했다. 이제 각 horse마다 가장 가까운 cow를 찾으면 되는데, 그 과정을 단순히 upper_bound로 교체했을 뿐인데 바로 Pass가 나와버려 얼탱이 없었다.

람다함수가 병목현상을 만드는지에 관해서는 좀 더 조사할 필요가 있다.

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  freopen("sample_input.txt", "r", stdin);

  int t = 0;
  cin >> t;

  for (int tc = 1; tc <= t; ++tc) {

    int n;
    int m;
    int c1;
    int c2;
    cin >> n >> m >> c1 >> c2;
    int dist_x = abs(c1 - c2);
    vector<int> cows;
    vector<int> horses;

    for (int i = 0; i < n; ++i) {
      int cow;
      cin >> cow;
      cows.push_back(cow);
    }
    // cow를 정렬하고 horse는 벡터에 넣지말고 바로 bin_search
    std::sort(cows.begin(), cows.end());

    int dist_z = std::numeric_limits<int>::max();
    int count = 0;

    auto evaluate = [&dist_z, &count](int dist) {
      if (dist < dist_z) {
        dist_z = dist;
        count = 1;
      } else if (dist == dist_z) {
        count += 1;
      }
    };

    for (int i = 0; i < m; ++i) {
      int horse;
      cin >> horse;

      // 어떤 말에 대하여 (말 <= 소) 조건을 만족시키는 첫번째 말을 고른다.
      // 그 말의 바로 이전 말과 비교하여 더 가까운 놈을 선택한다.
      auto cow_itr = std::upper_bound(cows.begin(), cows.end(), horse);
      if (cow_itr != cows.end()) {
        evaluate(abs(horse - *cow_itr));
      }
      if (cow_itr != cows.begin()) {
        evaluate(abs(horse - *(cow_itr - 1)));
      }
    }

    cout << "#" << tc << " " << dist_z + dist_x << " " << count << "\\n";
  }
  return 0;
}