[백준 2912] 백설공주와 난쟁이

[ghdcksgml1]

아이디어

사진에 찍힌 난쟁이의 정보가 주어졌을 때, 예쁜 사진인지 아닌지 알아내는 프로그램을 작성하는 문제이다.

모자의 색상이 주어지면 머지소트 트리로 바로 구하는게 가능하지만, 모자의 색상이 주어지지 않고 알아서 찾아야하기 때문에 문제 아이디어를 떠올리는게 매우 어려웠다.

사진에 찍힌 난쟁이 K명 중 K/2보다 많은 난쟁이의 모자색을 찾아야한다.

일단 잘 모르겠어서 무작정 머지소트 트리를 구현했다.

머지소트 트리를 구현하면 아래와 같이 나온다.

여기서 엄청난 규칙을 발견했다!!

리프 노드를 제외한 현재 노드가 2K개라고 할때, K,K-1 인덱스의 값이 같다면 그 값이 과반수일 가능성이 높다는 것이다. (무조건 과반수 이상 x)

현재 노드의 개수가 홀수개라면 K/2를 추가해준다.

시간 복잡도

일단 (3 ≤ N ≤ 300,000, 1 ≤ C ≤ 10,000, 1 ≤ M ≤ 10,000) 이기 때문에 C*M = 10⁸ 으로 시간 초과가 나게 된다.

머지소트 트리를 쓰면 시간복잡도와 공간복잡도 둘다 O(N logN)으로 구현할 수 있다.

이렇게 머지소트 트리를 구현하고나서 M번 동안의 예쁜사진을 인지 아닌지를 출력해야한다.

구현한 머지소트 트리를 이용하면 O(logN)만에 해당 모자를 쓴 난쟁이의 숫자를 구할 수 있다.

하지만, 난쟁이들의 모자색은 최대 10,000가지 이므로 만가지를 모두 다 탐색하게 된다면 O(MClogN) 으로 시간초과가 나게된다.

따라서 위에서 찾아낸 규칙을 이용해 과반수일 가능성이 높은 모자색만 탐색하게 된다면 O(M*log²N) 으로 시간복잡도를 줄일 수 있다.

---

// 언어 : C++ , (성공/실패) : 1/6 , 메모리 : 67680 KB , 시간 : 292ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h> // memset
#include <math.h>
#define SIZE 300010

using namespace std;


vector<int> mst[SIZE*4];
vector<int> tmp;
int N;
int arr[SIZE];

// 머지소트 트리 빌드
void buildRec(int node,int start,int end){
    vector<int> &cur = mst[node];
    if(start == end){
        cur.push_back(arr[start]);
        return;
    }
    int mid = (start + end) / 2;
    buildRec(node*2,start,mid);
    buildRec(node*2+1,mid+1,end);

    vector<int> &left = mst[node*2], &right = mst[node*2+1];
    cur.resize(left.size() + right.size());
    merge(left.begin(),left.end(),right.begin(),right.end(),cur.begin());
}

// 범위내의 해당 모자를 쓰고 있는 난쟁이의 수 출력
int queryRec(int left,int right,int node,int start,int end,int target){
    if(left>end || right<start) return 0;
    if(left<=start && end<=right){
        int temp = upper_bound(mst[node].begin(),mst[node].end(),target)- lower_bound(mst[node].begin(),mst[node].end(),target);
        return temp;
    }
    int mid = (start + end) / 2;
    return queryRec(left,right,node*2,start,mid,target) + queryRec(left,right,node*2+1,mid+1,end,target);
}

// 과반수일 가능성이 높은 모자색을 tmp에 추가시키는 함수
void queryRec2(int left,int right,int node,int start,int end){
    if(left>end || right<start) return ;
    if(left<=start && end<=right){
        int size = mst[node].size();
        if(start == end){tmp.push_back(arr[start]); return;}
        if(size%2 == 1){
            tmp.push_back(mst[node][size/2]);
        }else {
            if (mst[node][size / 2] == mst[node][size / 2 - 1]) {
                tmp.push_back(mst[node][size / 2]);
            }
        }
        return ;
    }
    int mid = (start + end) / 2;
    queryRec2(left,right,node*2,start,mid);
    queryRec2(left,right,node*2+1,mid+1,end);
}

int main(void){
    // 입출력 속도 최적화
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>N;int C;cin>>C;
    for(int i=1;i<=N;i++){
        cin>>arr[i];
    }

    buildRec(1,1,N);

    int M; cin>>M;
    for(int i=0;i<M;i++){
        int a,b; cin>>a>>b;
        if(a>b){
            int temp = a;
            a = b;
            b = temp;
        }
        bool trigger = false;
        tmp = {};
        queryRec2(a,b,1,1,N);
        for(int j=0;j<tmp.size();j++){
            if((b-a+1)/2 < queryRec(a,b,1,1,N,tmp[j])) {
                cout<<"yes "<<tmp[j]<<'\n';
                trigger = true;
                break;
            }
        }
        if(!trigger) cout<<"no"<<'\n';
    }

    return 0;
}