Baekjoon 5525 IOIOI

Link https://www.acmicpc.net/problem/5525

결과 2844KB / 12 ms

언어 C++ 17

 

풀이

Hash를 이용하여 문제를 해결

string을 이용한 방법으로도 해결 가능할 듯 보인다.

I를 1 O를 0인 2진수로 생각해 해시를 구성한다.

매 순간 특정 지점에서 해시를 구하면 string과 같은 복잡도가 나오거나 더 나오기 때문에

슬라이딩 윈도우처럼 값을 빼고 더하면서 해시를 구하면 O(n) 시간에 해시를 구할 수 있다.

비교할 해시랑 매 순간 구해지는 해시를 비교하면서 일치하는 개수를 구하면 된다.

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 1000000;
const int MOD = 100000007;

int targetHash = 1;
int topHash = 1;

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

	int n, s; cin >> n >> s;
	int res = 0;

	char input[MAX + 1] = {};
	cin >> input;

	bool trigger = true;
	for (int i = 0; i < n; i++)
		targetHash = ((targetHash * 4) + 1) % MOD;

	int hash = 0;
	for (int i = 0; i < 2 * n + 1; i++) {
		hash = (hash * 2 + (input[i] == 'I')) % MOD;
	}

	for (int i = 0; i < 2 * n; i++)
		topHash = (topHash * 2) % MOD;

	for (int i = 0; i < s - (2 * n); i++)
	{
		res += targetHash == hash;
		if (input[i] == 'I')
			hash = (hash - topHash) % MOD;
		if (hash < 0)
			hash += MOD;
		hash = ((hash * 2) + (input[i + (2 * n + 1)] == 'I')) % MOD;
	}

	cout << res;

	return 0;
}