[알고스팟][C++] ITES: 외계 신호 분석

문제 링크: https://algospot.com/judge/problem/read/ITES

(출처: 종만북)

 

투포인터로 문제를 풀 수 있습니다.

입력을 만드는 부분이 있는데, 난수 생성기(random number generator)를 만들면 간단하게 구현할 수 있습니다.

이 문제는 오프라인 알고리즘을 사용하려면 메모리가 부족합니다. 그래서 데이터의 일부만 갖고도 해결 가능한 온라인 알고리즘을 사용해야 합니다.

 

일단 문제를 투포인터로 풀 수 있는데요, 배열 인덱스 head, tail을 갖고 구간합을 이용해 인덱스를 조절하면 됩니다.

구간합이 k 이상이 될 때까지 tail을 옮기고, 이때 구간합이 k과 같은지 체크합니다. 그 다음 구간합에서 head값을 빼고, head를 한 칸 이동합니다. 이걸 반복하면 됩니다.

// 투포인터를 사용한 알고리즘
// (오프라인)
int optimized(vector<int>& signals, int k) {
	int ret = 0, tail = 0, rangeSum = signals[0];

	for (int head = 0; head < signals.size(); ++head) {
		//rangeSum이 k이상인 최초의 구간을 만날 때까지 tail을 옮긴다
		while (rangeSum < k && tail + 1 < signals.size())
			rangeSum += signals[++tail];

		if (rangeSum == k) ++ret;

		rangeSum -= signals[head];
	}

	return ret;
}

위 코드의 시간복잡도는 O(N)입니다.

이 알고리즘을 온라인 알고리즘으로 바꾸려면 어떻게 해야 할까요. head에서 tail까지 구간을 큐로 저장하면 됩니다.

구현을 좀 더 간단히 하기 위해, 구간에 무조건 원소를 추가하고 구간합이 k 이하가 될 때까지 원소를 빼는 식으로 구현하면 아래와 같습니다.

 

struct RNG {
	unsigned seed;
	RNG() : seed(1983) {}

	unsigned next() {
		unsigned ret = seed;
		seed = ((seed*214013u) + 2531011u);	//update seed
		return ret % 10000 + 1;
	}
};

int countRanges(int k, int n) {
	RNG rng;	//신호값을 생성하는 난수 생성기
	queue<int> range;	//현재 구간
	int ret = 0, rangeSum = 0;

	for (int i = 0; i < n; ++i) {
		// 숫자를 먼저 추가
		int newSignal = rng.next();
		rangeSum += newSignal;
		range.push(newSignal);

		// 구간합이 k이하가 될 때까지 숫자 제거
		while (rangeSum > k) {
			rangeSum -= range.front();
			range.pop();
		}

		if (rangeSum == k) ++ret;
	}

	return ret;
}

RNG는 난수 생성기입니다. 문제에서 \(2^{32}\)로 나눈 나머지를 사용하는데, unsigned int를 사용해 나머지 연산이 필요가 없게 됩니다.

큐의 크기는 k 이하이고 적은 양의 메모리로도 이 문제를 해결할 수 있게 됩니다.