[BOJ 6515 // C++] Frequent values

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 6515번 문제인 Frequent values이다.

문제는 아래 링크를 확인하자.

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

6515번: Frequent values

주어지는 수열이 단조증가한다는 조건을 확인하자.

 

수열이 단조증가하므로 이 수열의 모든 같은 수들은 서로 붙어있다. (사이에 다른 수를 두고 있을 수 없다.)

 

이를 이용하여, 1번 인덱스부터 i번 인덱스까지의 수열을 살폈을 때 i번 인덱스의 원소가 수열에서 몇번 등장했는지를 나타내는 배열을 만들어 쿼리가 들어올 때마다 이 배열의 구간에서의 최댓값을 구하는 것으로 문제를 대략 해결할 수 있다. 단, 배열의 범위의 앞부분은 연속된 수의 일부를 끊을 수 있으므로 이 부분에 대한 예외처리를 구현해주자.

 

이러한 작업을 할 수 있는 자료구조는 sparse table과 segment tree등이 있다.

 

지문 입력문단의 "The input consists of several test cases." 문장과 "The last test case is followed by a line containing a single 0." 가 무엇을 의미하는지 잘 생각하고, 글쓴이와 같은 허무한 이유로 문제를 틀리지 않기를 바란다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int arr[100001];
pair<int, int> seg[262145];

pair<int, int> init(int L, int R, int sI) {
	if (L == R) return seg[sI] = make_pair(arr[L], L);
	return seg[sI] = max(init(L, (L + R) / 2, sI * 2), init((L + R) / 2 + 1, R, sI * 2 + 1));
}

pair<int, int> rangemax(int L, int R, int qL, int qR, int sI) {
	if (qR < L || R < qL) return make_pair(-1, -1);
	if (qL <= L && R <= qR) return seg[sI];
	return max(rangemax(L, (L + R) / 2, qL, qR, sI * 2), rangemax((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, Q; cin >> N;
	while (N) {
		cin >> Q;
		int old = -1000000007, cnt = -1;
		for (int i = 1; i <= N; i++) {
			int x; cin >> x;
			if (x == old) cnt++;
			else old = x, cnt = 1;
			arr[i] = cnt;
		}

		init(1, N, 1);
		
		while (Q--) {
			int qL, qR; cin >> qL >> qR;
			pair<int, int> qAns = rangemax(1, N, qL, qR, 1);
			if (qAns.second - qL + 1 < qAns.first) {
				if (qAns.second < qR) cout << max(qAns.second - qL + 1, rangemax(1, N, qAns.second + 1, qR, 1).first) << '\n';
				else cout << qAns.second - qL + 1 << '\n';
			}
			else cout << qAns.first << '\n';
		}

		cin >> N;
	}
}