[BOJ 23719] K번째 음식 찾기 1

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

23791번: K번째 음식 찾기 1

Tag : binary search

 

문제요약

정렬된 배열 a, b가 입력으로 주어지고 쿼리마다 a[1 : p], b[1 : q]에서 k번째 수를 찾는 문제다.

 

풀이

먼저 a의 인덱스를 기준으로 이분탐색을 진행한다. 

결정함수 chk(m) := a[1 : p], b[1 : q]에서 a[m]이 k번째 수 이상이면 true 

b에 k번째 수가 있으면 a, b를 뒤집어서 다시 답을 구하면 됩니다.

+ 사실 한번 더 돌리지 않고 바로 구할 수 있는 방법도 있다.

   이분탐색이 끝난 후 chk(m)을 만족하는 최소 위치가 hi 일테니 b[k - hi + 1]을 구하면 된다. 

총 시간복잡도는 이분탐색의 \(O(log) \times \)결정함수의 구하는 시간복잡도일 것이다.

 

결정함수를 \(O(logn)\)에 구하는 첫번째 방법은 다음과 같다.

1. a[m]이 k번째 수 이상이 되기 위해선 b에서 a[m] 이하인 수가 k - m개 이상이어야 한다.

2. 따라서 b에서 a[m]의 upper_bound를 구하고 이것이 k - m이상인지 구한다.

 

두번째로 결정함수를 \(O(1)\)에 구하는 방법이 있다. 

1. a[m]이 k번째 수 이상이 되기 위해선 b[k - m]이 a[m] 이하이면 된다. 

2. 인덱스를 벗어나는지 잘 체크하고 1을 수행하면 된다. 

 

난이도 투표 대부분은 로그 제곱 기준으로 투표가 되었고 로그 풀이가 정해이려면 골드 1 ~ 2 정도가 아닐까? 생각한다.

 

 

전체코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

int N,Q;
int p,q,k;

int bs(vector<ll>&a,vector<ll>&b){
    int lo=0,hi=p+1;
    while(lo+1<hi){
        int m=(lo+hi)/2,j=k-m;
        if((1<=j and j<=q and b[j]<=a[m]) or j<=0)hi=m;
        else lo=m;
    }
    return hi;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>N;
    vector<ll>a(N+2),b(N+2);
    for(int i=1;i<=N;i++)cin>>a[i];
    for(int i=1;i<=N;i++)cin>>b[i];
    cin>>Q;
    for(int i=1;i<=Q;i++){
        cin>>p>>q>>k;
        int hi=bs(a,b);
        int cnt=(int)(upper_bound(b.begin()+1,b.begin()+q+1,a[hi])-b.begin()-1);
        if(hi!=p+1 and cnt==k-hi){
            cout<<1<<' '<<hi<<endl;
            continue;
        }
        swap(p,q);
        hi=bs(b,a);
        cnt=(int)(upper_bound(a.begin()+1,a.begin()+p+1,b[hi])-a.begin()-1);
        cout<<2<<' '<<hi<<endl;
    }
}