백준 7469번 K번째 수 (boj/7469.c)

* 글을 잘못읽어서 오버스펙인 코드를 만들어버렸다..... 배열에 "서로 다른" 수 N개라 했는데..... 왜 수가 같은 경우를 상정했는지.... 어휴

 

세그먼트 트리를 조금 새롭게 응용하는 문제입니다. 세그먼트 트리 + 부분정렬 + 특수이진탐색을 사용합니다.

어떤 범위에서 수 A가 K번째 수라는 의미는, 그 범위에서 A보다 작거나 같은 수가 K-1개 있다는 뜻입니다.

 

더 정확하게 들어가보자면, 어떤 범위에서 A보다 작은 수가 omin개, A보다 작거나 같은 수가 omax개 있다면, 

수 A는 범위에서 omin+1번째 ~ omax번째 수가 됩니다.

 

이때 omin+1 <= K and omax<=K가 성립하면, A는 범위에서 K번째 수가 될 수 있습니다.

 

공간복잡도 NlogN, 시간복잡도 M(logN)^2으로 풀 수 있습니다. 소스는 아래와 같습니다.

#include <stdio.h>
#include <string.h>
#define ARR_W   100000
#define ARR_H   20
int N;
int qsort[ARR_H][ARR_W] = { 0, };
int bnsrcM(int* arr, int sze, int data){
    int lft=0, rht=sze-1, mid;
    for(mid=(lft+rht)/2;lft<=rht;mid=(lft+rht)/2){
        if(mid==sze-1){ return (arr[mid]<=data)?sze:sze-1; }
        if(arr[mid]<=data && arr[mid+1]>data){ return mid+1; }
        else if(arr[mid]>data){ rht=mid-1; }
        else{ lft=mid+1; }
    } return 0;
}
int bnsrcm(int* arr, int sze, int data){
    int lft=0, rht=sze-1, mid;
    for(mid=(lft+rht)/2;lft<=rht;mid=(lft+rht)/2){
        if(mid==sze-1){ return (arr[mid]<data)?sze:sze-1; }
        if(arr[mid]<data && arr[mid+1]>=data){ return mid+1; }
        else if(arr[mid]>=data){ rht=mid-1; }
        else{ lft=mid+1; }
    } return 0;
}
int suiteM(int rnk, int s, int e, int v){
    int idx, lft, rht, mid;
    idx = s>>rnk;
    lft=idx<<rnk; rht=lft+(1<<rnk)-1; mid=(lft+rht)/2;
    if(rht>=N){ rht=N-1; }
    if(s==lft && e==rht){
        if(rnk==0){ return qsort[rnk][s]<=v; }
        else { return bnsrcM(&qsort[rnk][s], rht-lft+1, v); }
    }
    if(e<=mid || mid<s){ return suiteM(rnk-1, s, e, v); }
    else{ return suiteM(rnk-1, s, mid, v)+suiteM(rnk-1, mid+1, e, v); }
}
int suitem(int rnk, int s, int e, int v){
    int idx, lft, rht, mid;
    idx = s>>rnk;
    lft=idx<<rnk; rht=lft+(1<<rnk)-1; mid=(lft+rht)/2;
    if(rht>=N){ rht=N-1; }
    if(s==lft && e==rht){
        if(rnk==0){ return qsort[rnk][s]<v; }
        else{ return bnsrcm(&qsort[rnk][s], rht-lft+1, v); }
    }
    if(e<=mid || mid<s){ return suitem(rnk-1, s, e, v); }
    else{ return suitem(rnk-1, s, mid, v)+suitem(rnk-1, mid+1, e, v); }
}
int Q(int s, int e, int k){
    int lft=0, rht=N-1, mid;
    int omax, omin;
    int cur;
    for(mid=(lft+rht)/2;lft<=rht;mid=(lft+rht)/2){
        cur=qsort[ARR_H-1][mid];
        omax=suiteM(ARR_H-1, s, e, cur);
        omin=suitem(ARR_H-1, s, e, cur);
        if(omax==omin){
            if(omax<k){ lft=mid+1; }
            else{ rht=mid-1; }
            continue;
        }
        if(omin+1<=k && k<=omax){ return cur; }
        else if(k<omin+1){ rht=mid-1; }
        else{ lft=mid+1; }
    } return -1;
}
int main(void){
    int M;
    int lft, mid, rht;
    int sze, lidx, ridx;
    int s, e, k;
    scanf("%d %d", &N, &M);
    for(int i=0;i<N;i++){ scanf("%d", &qsort[0][i]); }
    for(int rnk=1;rnk<ARR_H;rnk++){
        for(lft=0;lft<N;lft+=1<<rnk){ 
            rht=lft+(1<<rnk)-1; mid=(lft+rht)/2;
            lidx=lft; ridx=mid+1;
            if(rht>=N){
                rht=N-1; sze=N-lft;
                if(rht<=mid){ memcpy(&qsort[rnk][lft], &qsort[rnk-1][lft], sizeof(int)*sze); continue; } }
            else{ sze=1<<rnk; }
            for(int j=0;j<sze;j++){
                if(lidx>mid || (ridx<=rht && qsort[rnk-1][ridx]<qsort[rnk-1][lidx])){ qsort[rnk][lft+j]=qsort[rnk-1][ridx++]; }
                else{ qsort[rnk][lft+j]=qsort[rnk-1][lidx++]; } }
        }
    }
    for(int i=0;i<M;i++){
        scanf("%d %d %d", &s, &e, &k);
        printf("%d\n", Q(--s, --e, k)); }
    return 0;
}

그리고 이 M계 함수는 m계 함수를 대체할 수 있기 때문에 코드를 더 줄일 수있습니다.

#include <stdio.h>
#include <string.h>
#define ARR_W   100000
#define ARR_H   20
int N;
int qsort[ARR_H][ARR_W] = { 0, };
int bnsrcM(int* arr, int sze, int data){
    int lft=0, rht=sze-1, mid;
    for(mid=(lft+rht)/2;lft<=rht;mid=(lft+rht)/2){
        if(mid==sze-1){ return (arr[mid]<=data)?sze:sze-1; }
        if(arr[mid]<=data && arr[mid+1]>data){ return mid+1; }
        else if(arr[mid]>data){ rht=mid-1; }
        else{ lft=mid+1; }
    } return 0;
}
int suiteM(int rnk, int s, int e, int v){
    int idx, lft, rht, mid;
    idx = s>>rnk;
    lft=idx<<rnk; rht=lft+(1<<rnk)-1; mid=(lft+rht)/2;
    if(rht>=N){ rht=N-1; }
    if(s==lft && e==rht){
        if(rnk==0){ return qsort[rnk][s]<=v; }
        else { return bnsrcM(&qsort[rnk][s], rht-lft+1, v); }
    }
    if(e<=mid || mid<s){ return suiteM(rnk-1, s, e, v); }
    else{ return suiteM(rnk-1, s, mid, v)+suiteM(rnk-1, mid+1, e, v); }
}
int Q(int s, int e, int k){
    int lft=0, rht=N-1, mid;
    int omax, omin;
    int cur;
    for(mid=(lft+rht)/2;lft<=rht;mid=(lft+rht)/2){
        cur=qsort[ARR_H-1][mid];
        omax=suiteM(ARR_H-1, s, e, cur);
        omin=suiteM(ARR_H-1, s, e, cur-1);
        if(omax==omin){
            if(omax<k){ lft=mid+1; }
            else{ rht=mid-1; }
            continue;
        }
        if(omin+1<=k && k<=omax){ return cur; }
        else if(k<omin+1){ rht=mid-1; }
        else{ lft=mid+1; }
    } return -1;
}
int main(void){
    int M;
    int lft, mid, rht;
    int sze, lidx, ridx;
    int s, e, k;
    scanf("%d %d", &N, &M);
    for(int i=0;i<N;i++){ scanf("%d", &qsort[0][i]); }
    for(int rnk=1;rnk<ARR_H;rnk++){
        for(lft=0;lft<N;lft+=1<<rnk){ 
            rht=lft+(1<<rnk)-1; mid=(lft+rht)/2;
            lidx=lft; ridx=mid+1;
            if(rht>=N){
                rht=N-1; sze=N-lft;
                if(rht<=mid){ memcpy(&qsort[rnk][lft], &qsort[rnk-1][lft], sizeof(int)*sze); continue; } }
            else{ sze=1<<rnk; }
            for(int j=0;j<sze;j++){
                if(lidx>mid || (ridx<=rht && qsort[rnk-1][ridx]<qsort[rnk-1][lidx])){ qsort[rnk][lft+j]=qsort[rnk-1][ridx++]; }
                else{ qsort[rnk][lft+j]=qsort[rnk-1][lidx++]; } }
        }
    }
    for(int i=0;i<M;i++){
        scanf("%d %d %d", &s, &e, &k);
        printf("%d\n", Q(--s, --e, k)); }
    return 0;
}