[BOJ/Platinum 2] 백준 2912 백설공주와 난쟁이(C++)

문제 링크

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

2912번: 백설공주와 난쟁이

 

 

문제

백설 공주와 난쟁이 N명과 함께 숲 속에 살고 있다. 난쟁이는 매일 광산에 일하러가고, 백설 공주는 그동안 페이스북을 하고 있다.

매일 아침 난쟁이는 한 줄로 휘파람을 불면서 광산으로 출근을 한다. 백설 공주는 그 주변을 돌아다니면서 난쟁이들 사진을 찍는다.

난쟁이가 광산에 들어가면, 백설 공주는 다시 집으로 돌아간다. 집으로 돌아가면서 찍은 사진 중에 페이스북에 올릴 예쁜 사진을 고른다. 각 난쟁이는 모두 모자를 쓰고 있다. 모자의 색상은 총 C가지가 있다. 사진에 찍힌 난쟁이가 쓰고 있는 모자의 색상 중 절반보다 많은 색이 같은 색이라면 예쁜 사진이다. 즉, 사진에 난쟁이가 K명 찍혀있고, K/2보다 많은 난쟁이의 모자 색이 같다면 예쁜 사진이다.

백설공주가 찍은 사진 M개와 각 사진에 찍힌 난쟁이가 주어졌을 때, 예쁜 사진인지 아닌지를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 난쟁이의 수 N과 모자 색상의 수 C가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ C ≤ 10,000)

둘째 줄에는 각 난쟁이가 쓰고 있는 모자의 색상이 줄을 서 있는 순서대로 주어진다. 색상은 C이하의 자연수로 나타낸다.

셋째 줄에는 사진의 수 M이 주어진다. (1 ≤ M ≤ 10,000)

다음 M개 줄에는 두 정수 A와 B가 주어진다. (1 ≤ A ≤ B ≤ N) 이 줄은 사진의 정보를 의미하고, A번째 난쟁이부터 B번째 난쟁이까지 사진에 찍혔다는 뜻이다.

출력

출력은 총 M 줄이다. 각 사진이 예쁘지 않다면 "no"를 출력하고, 예쁘다면 "yes X"를 출력한다. 예쁜 사진인 경우에 X는 사진에 절반이 넘는 모자의 색상이다.

예제 입력 1

10 3
1 2 1 2 1 2 3 2 3 3
8
1 2
1 3
1 4
1 5
2 5
2 6
6 9
7 10

예제 출력 1

no
yes 1
no
yes 1
no
yes 2
no
yes 3

알고리즘 분류

• 평행 분할

풀이

길이가 30만인 수열의 특정 구간 내에 등장하는 색상의 개수를 구하는 작업을 1초 안에 1만번이나 수행하기에는 무리가 있어 모스 알고리즘을 통해 해결한다.

우선 M개의 쿼리문을 구간의 시작과 끝, 그리고 쿼리문 자체의 Index 변수를 갖는 구조체로서 벡터에 저장하고, 구간의 시작 Index를 √ N로 나눈 값에 따라 오름차순으로 정렬한다. 만약 그 값이 같은 경우에는 구간의 끝 Index에 따라 오름차순으로 정렬한다.

이제 각 쿼리문마다 해당하는 정답을 구한다. 먼저 첫 번째 쿼리문에 해당하는 구간을 전부 탐색하면서 등장하는 색상의 개수를 증가시킨다.

구간을 전부 탐색한 후, 색상의 개수가 1만개이기 때문에 1부터 10,000까지 모든 색상의 등장 횟수를 탐색하는 것은 오랜 시간이 걸리지 않는다. 모든 색상 중에서 구간 길이의 절반이 넘는 개수를 가진 색상이 현재, 즉 첫 번째 쿼리문의 Index번째에 해당하는 정답이 된다.

이제부터는 M-1개의 쿼리문에 해당하는 정답을 전부 구한다. 현재 지정된 구간의 시작과 끝을 현재 쿼리문에 해당하는 구간으로 맞춰가면서 원소를 추가하거나 제외시킨다. 작업이 모두 끝나면 나오는 값이 현재 쿼리문의 Index번째에 해당하는 정답이 되고, 다음 쿼리문으로 넘어간다.

마지막으로 M개의 정답을 출력하는데, 정답이 -1이면 현재 구간에서는 길이의 절반 이상 등장하는 색상이 존재하지 않는다는 뜻이므로 no를 출력한다. -1이 아니라면 그 값이 해당 구간에서 절반 이상 등장하는 색상이므로 yes X를 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#define MAX_N 300001
#define MAX_C 10001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct QUERY {
    int Left, Right, Index;
};

int N, C, M, S, A, B;
int Color[MAX_N];
vector<QUERY> Query;
int Left, Right, Value, Which;
int Count[MAX_C], Count_Count[MAX_N];
int Answer[MAX_C];

void init() {
    for (int i = 0; i < MAX_C; i++) {
        Answer[i] = -1;
    }
}

void input() {
    cin >> N >> C;
    for (int i = 0; i < N; i++) {
        cin >> Color[i];
    }
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> A >> B;
        Query.push_back({ A - 1,B - 1,i });
    }
}

bool Comp(QUERY A, QUERY B) {
    if (A.Left / S != B.Left / S) {
        return (A.Left / S < B.Left / S);
    }
    return (A.Right < B.Right);
}

void settings() {
    S = sqrt(N);
    sort(Query.begin(), Query.end(), Comp);
    Left = Query[0].Left;
    Right = Query[0].Right;
    for (int i = Left; i <= Right; i++) {
        int Now = Color[i];
        Count[Now]++;
    }
    for (int i = 1; i < MAX_C; i++) {
        if (Count[i] * 2 > (Right - Left + 1)) {
            Answer[Query[0].Index] = i;
            break;
        }
    }
    for (int i = 1; i < M; i++) {
        while (Query[i].Left < Left) {
            Left--;
            int Now = Color[Left];
            Count[Now]++;
        };

        while (Query[i].Left > Left) {
            int Now = Color[Left];
            Count[Now]--;
            Left++;
        };

        while (Query[i].Right > Right) {
            Right++;
            int Now = Color[Right];
            Count[Now]++;
        };

        while (Query[i].Right < Right) {
            int Now = Color[Right];
            Count[Now]--;
            Right--;
        };

        for (int j = 1; j < MAX_C; j++) {
            if (Count[j] * 2 > (Query[i].Right - Query[i].Left + 1)) {
                Answer[Query[i].Index] = j;
                break;
            }
        }
    }
}

void find_Answer() {
    for (int i = 0; i < M; i++) {
        if (Answer[i] != -1) {
            cout << "yes " << Answer[i] << "\n";
        }
        else {
            cout << "no\n";
        }
    }
}

int main() {
    FASTIO
    init();
    input();
    settings();
    find_Answer();

    return 0;
}