백준 23792 - K번째 음식 찾기 2 (C++)

문제

• 문제 링크

  
   BOJ 23792 - K번째 음식 찾기 2 
  

• 문제 요약

$x$ $y$ $z$ $k$ : 한식 $[1..x]$, 양식 $[1..y]$, 중식 $[1..z]$ 중에 $k$번째로 맛있는 음식 $?$


한식, 양식, 중식 각각 $N$개의 음식에 대한 맛이 주어진다.
위의 쿼리가 $Q$개 주어질 때, 각각에 맞는 답을 출력하자.

• 제한

TL : $2$ sec, ML : $512$ MB




$1 ≤ N, Q ≤ 10^5$

$1 ≤ A_x, B_y, C_z ≤ 2^{31} - 1$

$3N$개 음식의 맛은 모두 서로 다르다.

알고리즘 분류

• 이분 탐색(binary search)
• 매개 변수 탐색(parametric search)

풀이

K번째 음식 찾기 1 을 처음 보고 무지성 $merge$-$sort$ $tree$ 로 문제를 풀까 했는데,
본문 내용 자체가 특정 유형의 문제임을 노골적으로 알려주고 있어서 쉽게 방향을 잡을 수 있었다.
이번 문제 역시 $1$을 풀고 왔다면 알겠지만 별반 다를 게 없다.

우리는 단조성을 갖는 배열들에 대해 이분 탐색을 적용해볼 수 있다.
임의의 배열에 대해 다음과 같이 결정 문제를 정의해보자.

$Decision(m)$ : 현재 기준이 되는 배열에서, $m$번째 요소가 답이 될 수 있는가$?$

이와 같이 정의할 경우, 배열이 총 $3$개 이므로 결정 함수의 호출도 최대 $3$번 이뤄질 수 있다.

이제 결정 문제를 어떻게 풀 지만이 남았다.
아래의 과정을 따라가자.

---

• 현재 기준 배열을 $array$라 할 때, 기본적으로 $array$에서 $m+1$개의 요소를 제친 상태이다.(자신 포함)
• 즉, 나머지 두 배열에서 $array[m]$보다 작은 요소들의 개수 합은 $k-m-1$개여야만 한다.
• 이때 두 배열 내에서 $array[m]$보다 큰 수가 처음으로 등장하는 위치는 이분 탐색으로 찾아줄 수 있다.
• 그렇게 추려진 값이 $k$와 같다면 답을 찾은 것이 되겠다.
• 작다면 좀 더 큰 $m$을 봐야 한다는 것, 크다면 좀 더 작은 $m$을 봐야 한다는 것이 자명하다.

결과적으로 적당한 $m$을 찾는 데에 $O(logN)$, 각 $m$에서 결정 문제를 푸는 데에 $O(logN)$이 소요 되므로 문제를 총 $O(Qlog^2N)$에 풀 수 있게 된다.

$AC$를 받은 후 생각해봤는데, 어떤 배열의 $m$에 대해 $k$와 같아지기 위해 필요한 요소의 수는 인덱스 계산을 통해 구할 수 있다.
즉, 결정 문제를 푸는 과정에서 이분 탐색을 쓰지 않아도 된다.

구현은 조금 더 까다로워질 수 있겠지만 이 경우 $O(QlogN)$에 문제를 풀 수 있을 듯 하다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
using V = vector <int>;
 
int Decision(V& A, V& B, V& C, int n, int k, int o, int x, int y, int z)
{
    int l{}, r(x - 1);
    while (l <= r)
    {
        int m(l + r >> 1), cur(m + 1);
        cur += lower_bound(B.begin(), B.begin() + y, A[m]) - B.begin();
        cur += lower_bound(C.begin(), C.begin() + z, A[m]) - C.begin();
        if (cur == k)
        {
            cout << o << ' ' << m + 1 << '\n';
            return 1;
        }
        cur > k ? r = m - 1 : l = m + 1;
    }
    return 0;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
 
    vector <int> A(n), B(n), C(n);
    for (int& i : A) cin >> i;
    for (int& i : B) cin >> i;
    for (int& i : C) cin >> i;
 
    int q; cin >> q;
    for (int x, y, z, k; q--;)
    {
        cin >> x >> y >> z >> k;
        if (Decision(A, B, C, n, k, 1, x, y, z));
        else if (Decision(B, A, C, n, k, 2, y, x, z));
        else Decision(C, A, B, n, k, 3, z, x, y);
    }
}

comment

끝