<Baekjoon> # 1593 Sliding Window_문자해독 c++

문제

Idea

• 문자열 S안에서 단어W의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 계산
• 문자열 W의 길이가 g라고 했을 때, 문자열 S에서 g만큼 떼서 보았을 때 그 문자열을 구성하는 각 글자들이 W를 구성하는 각 글자들과 동일한지 살펴본다
• 문자열 S의 처음부터 g길이만큼 차례대로 탐색하므로 Sliding Window 기법을 사용

Sliding Window?

• 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제 풀이
• 배열이나 리스트 요소의 일정 범위 값을 비교할 때 사용
• 투 포인터와 비슷하지만 고정 사이즈* 윈도우를 사용한다는 차이가 있음

Initialise

• 문자열 W을 저장, 문자열 S에서 문자열 W이 길이만큼의 임시 문자열을 저장할 해쉬 맵을 만들어 준다

• 문자열 W에서 알파벳 종류의 개수, 임시 문자열에서 알파벳 종류의 개수를 저장해준다

  map<char, int> origin;
  map<char, int> tmp;
  
  int w_kind = 0; // w문자열의 종류
  int s_kind = 0; // s문자열의 종류
  
  for (int i = 0; i < N; i++) {
      if (origin.find(W[i]) == origin.end()) {
          origin[W[i]] = 1;
          w_kind++;
      }
      else
          origin[W[i]]++;
  }
  
  // s문자열에서 처음 n개의 문자에 대해 계산
  
  for (int i = 0; i < N; i++) {
      if (tmp.find(S[i]) == tmp.end()) {
          tmp[S[i]] = 1;
          s_kind++;
      }
      else
          tmp[S[i]]++;
  }

Sliding Window

• 문자열 W의 길이 N만큼 윈도우 크기로 설정

  int Start = 0;
  int End = N - 1;

• End 가 문자열 S의 길이 (M-1)일때 까지만 반복해서 윈도우를 옮겨준다
• 탐색 중 문자열 W에 있는 알파벳 종류 (w_kind)와 임시 문자열에 있는 알파벳 종류 (s_kind)가 같다면 이 두 문자열의 순열이 같은지 계산
• 윈도우를 한 칸 씩 옮겨주며 해쉬 맵에 있는 값을 변경해준다

Source Code

#include <iostream>
#include <map>

using namespace std;

int N, M;
string W, S;
map<char, int> origin;
map<char, int> tmp;

int w_kind = 0; // w문자열의 종류
int s_kind = 0; // s문자열의 종류
int ans = 0;


void sliding_window() {
	int Start = 0;
	int End = N - 1;

	while (1) {
		if (s_kind == w_kind) {
			bool check = true;
			for (int i = Start; i <= End; i++) {
				if (tmp[S[i]] != origin[S[i]]) {
					check = false;
					break;
				}
			}
			if (check) ans++;
		}

		if (tmp[S[Start]] == 1) {
			tmp.erase(S[Start]);
			s_kind--;
		}
		else tmp[S[Start]]--;

		Start++; End++;
		if (End >= M) break;

		if (tmp.find(S[End]) == tmp.end()) {
			tmp[S[End]] = 1;
			s_kind++;
		}
		else tmp[S[End]]++;
	}
}

void input() {
	cin >> N >> M;
	cin >> W >> S;

	for (int i = 0; i < N; i++) {
		if (origin.find(W[i]) == origin.end()) {
			origin[W[i]] = 1;
			w_kind++;
		}
		else
			origin[W[i]]++;
	}

	// s문자열에서 처음 n개의 문자에 대해 계산

	for (int i = 0; i < N; i++) {
		if (tmp.find(S[i]) == tmp.end()) {
			tmp[S[i]] = 1;
			s_kind++;
		}
		else
			tmp[S[i]]++;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	input();
	sliding_window();

	cout << ans << endl;
	return 0;
}