백준 1593 : 문자 해독

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

1593번: 문자 해독

 

슬라이딩 윈도우 알고리즘으로 해결하는 문제다.

문자열을 탐색하는 문제라 처음에는 라빈카프 알고리즘으로 순서를 상관하지 않고 시간 내에 문제를 해결할 수 없을까 고민하다가 해당 캐릭터의 아스키코드 값의 제곱을 더해서 해싱하는 방법을 떠올렸는데, 이렇게 할 시 너무 쉽게 해쉬 충돌이 발생한다.

 

예를 들어 "awr" 과 "zcm"은 시그마 제곱으로 해싱할 시 해쉬 값이 같다.

hash("awr") = (97 ^ 2) + (119 ^ 2) + (114 ^ 2) = 9409 + 14161 + 12996 = 36,566

hash("zcm") = (122 ^ 2) + (99 ^ 2) + (109 ^ 2) = 14884 + 9801 + 11881 = 36,566

 

따라서 정답이 되는 경우가 아닌데도 정답을 체크해서 틀리게 된다. 참고로 약간 오기가 생겨서 세제곱, 네제곱도 제출해봤는데 세제곱은 마찬가지로 해쉬 충돌로 오답 처리가 되고 네제곱으로 해싱할 시 정답 처리가 되었다. ㅋㅋㅋㅋㅋ

 

그래도 정해는 아니니 지금부터 설명할 정해로 풀도록 하자.

 

정해는 슬라이딩 윈도우 알고리즘으로, 한 칸씩 이동하면서, 빠지는 문자가 찾는 문자열에 매칭되는 문자였는지, 들어오는 문자가 찾는 문자열에 매칭되는 문자인지 확인해서 그 개수를 세어주면 된다.

 

#include <iostream>
#include <string>

using namespace std;

void solution() {
	int g, n;
	int cnt = 0, ans = 0;
	char cur;
	string s, w;

	//각각 w와 윈도우 안의 s에 있는 각각의 캐릭터의 개수를 저장할 배열
	int char_w[128] = { 0, }, char_s[128] = { 0, };

	cin >> g >> n >> w >> s;
	for (int i = 0; i < g; i++) {
		++char_w[w[i]];
	}
    //윈도우 안에 첫 g개의 문자를 삽입
	for (int i = 0; i < g; i++) {
		cur = s[i];
		++char_s[cur];
        //char_s가 char_w보다 작거나 같은 동안은 매칭되는 문자이므로 ++cnt
		if (char_s[cur] <= char_w[cur]) ++cnt;
	}

	//만약 매칭되는 문자의 수가 g와 같다면 정답 개수 증가
	if (cnt >= g) ++ans;
	for (int i = g; i < n; i++) {
    	//앞에서 문자 하나 제거
		cur = s[i - g];
        //여기서 char_w[cur]이 0이 아닌지 확인하는 부분은 없어도 동작한다.
		if (char_w[cur] && char_s[cur] <= char_w[cur]) --cnt;
		--char_s[cur];

		//뒤에 문자 하나 추가
		cur = s[i];
		++char_s[cur];
		if (char_w[cur] && char_s[cur] <= char_w[cur]) ++cnt;
		if (cnt >= g) ++ans;
	}

	cout << ans;
}

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

	return 0;
}

메모리: 7544 kb

시간: 32 ms

 

그리고 참고용으로 해싱으로 푼 코드도 올린다. 시간 차이가 매우 많이 나는 것을 확인할 수 있다.

#include <iostream>
#include <string>
#include <cmath>

using namespace std;
using ll = long long;

void solution() {
	int g, n;
	ll ans = 0, hash_w = 0, hash_s = 0;
	string s, w;
	int pow_n = 4;
    
	cin >> g >> n >> w >> s;
	for (int i = 0; i < g; i++) {
		hash_w += pow(w[i], pow_n);
		hash_s += pow(s[i], pow_n);
	}

	if (hash_w == hash_s) ++ans;
	for (int i = g; i < n; i++) {
		hash_s -= pow(s[i - g], pow_n);
		hash_s += pow(s[i], pow_n);
		if (hash_w == hash_s) ++ans;
	}
	
	cout << ans;
}

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

	return 0;
}

메모리: 7732 kb

시간: 412 ms