[백준] 2912번 백설공주와 난쟁이 C++ 코드

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <queue>

using namespace std;
struct Query {
	int L, R, idx;
};
const int MAX_N = 300003;
int n, c, a[MAX_N], m, max_cnt, max_num, freq[10001];

void add(int x) {
	freq[x]++;
}

void remove(int x) {
	freq[x]--;
}

void FASTIO() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

int main() {
	FASTIO();
	cin >> n >> c;
	for (int i = 0; i < n; i++) cin >> a[i];
	int block_size = sqrt(n);
	cin >> m;
	vector<Query> queries(m);
	vector<pair<int, int>> res(m);
	for (int i = 0; i < m; i++) {
		cin >> queries[i].L >> queries[i].R;
		queries[i].L--; // 0-based
		queries[i].R--; // 0-based
		queries[i].idx = i;
	}
    // mo's를 위한 정렬
	sort(queries.begin(), queries.end(), [block_size](Query a, Query b) {
		if (a.L / block_size != b.L / block_size) return a.L / block_size < b.L / block_size;
		return a.R < b.R;
	});
    // mo's
	int currentR = -1, currentL = 0;
	for (int i = 0; i < m; i++) {
		int r = queries[i].R;
		int l = queries[i].L;
		while (currentR < r) add(a[++currentR]);
		while (currentR > r) remove(a[currentR--]);
		while (currentL < l) remove(a[currentL++]);
		while (currentL > l) add(a[--currentL]);
		int num = 0; // yes no 판별
		int inum = 0; // 몇 번 모자인지 저장할 값
		int cnt = (r - l + 1);
		// c <= 10000 라 브루트포스로 탐색
        for (int j = 1; j <= c; j++) {
            if (freq[j] * 2> cnt) {
                num = 1; // 만약 찾으면 1을 저장해서 yes 출력
                inum = j;
                break;
            }
        }
        // 값 저장
		res[queries[i].idx] = { num, inum };
	}
	for (const auto& a : res) {
		if (a.first == 1) cout << "yes " << a.second << '\n';
		else cout << "no\n";
	}
	return 0;
}

풀이

m이 10000이고 c가 10000이라서 브루트포스로 찾아볼까 했던 문제. Mo's를 이용해서 모자 개수를 업데이트하고, for문을 순회하면서 절반 이상인 모자가 있는지 없는지 확인하면 된다. 새로 배운 점은 / 2를 하기보다 *2를 해서 찾는 게 더 직관적이라는 것이었다. Mo's를 배울 수 있었던 문제.