[G5] 백준 1593번 문자 해독 C++ 슬라이딩 윈도우, 구현, 문자열

리뷰

 

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

그리디한 접근 시 시간 초과가 났다. for문 한줄로 완탐을 끝낼 수 있는 방법을 많이 연구 해야할 것 같다.

 

전역 변수

• n, m, ans : 문자열 a의 길이 n, 문자열 b의 길이 m, 정답 저장용 변수 ans
• a, b : 입력으로 주어지는 첫번째 문자열 a, 두번째 문자열 b
• av : a문자열이 보유하고 있는 문자의 개수 정보 배열, 52크기로 세팅한다.
• bv : b문자열의 보유하고 있는 문자의 개수 정보 배열, 마찬가지로 52크기로 세팅

 

함수

1. chk

int chk()

 

현재 부분문자열이 일치하는지 여부를 체크하기 위한 함수

1. av와 bv의 모든 인덱스에 저장된 값이 동일한지 체크해 주어야 한다.
2. 만약 다른 값을 만났다면 0을 리턴해 주면되고, for문 종료때 까지 리턴되지 않았다면 1을 리턴한다.

 

2. To_index

int To_index(const char& ch)

 

문자를 av, bv배열의 인덱스로 변환해 주기 위한 함수

1. 소문자의 경우 0 ~ 25, 대문자의 경우 26 ~ 51의 인덱스를 사용할 것이다.
2. 따라서 매개변수 ch가 소문자라면 ch - 'a'를, 대문자라면 ch - 'A' + 26을 리턴해 준다.

 

문제풀이

1. n, m, a, b값을 입력 받아주고, n번의 반복문을 개행해 준다.
2. To_index함수를 통해 a[i], b[i]를 매개변수로 전달하여 리턴값을 각각 av, bv배열의 인덱스로 사용하여 초기화 해준다.
3. 초깃값을 체크하기 위해 chk함수를 한번 돌려준다, 리턴값을 ans에 더해주면 된다.
4. n ~ m - 1번의 반복문을 수행하고 bv에 현재 문자 정보를 더해주어 최신화 해준다.
5. 반대로 이미 사용한 문자인 i - n번째 문자는 감소시켜 준다.
6. chk함수를 통해 일치하는지 여부를 체크하고 그 리턴값을 ans에 더해준다.
7. 모든 탐색이 마치면 ans에 저장된 값을 출력해 준다.

 

참고 사항

처음에는 while과 for문을 적절히 섞어 상태를 체크하고 인덱스를 점프 뛰어주는 방법을 생각했다.

하지만 슬라이딩 윈도우를 쓰는 방법이 for문 1개와 적절한 함수로 반복을 줄일 수 있다.

 

 

정답 코드

#include<iostream>
#include<string>

using namespace std;

int n, m, ans;
string a, b;

int av[52];
int bv[52];

int chk() {
	for (int i = 0; i < 52; i++) if (av[i] != bv[i]) return 0;
	return 1;
}

int To_index(const char& ch) {
	if ('a' <= ch && ch <= 'z') return ch - 'a';
	return ch - 'A' + 26;
}

int main() {
	cin >> n >> m >> a >> b;

	for (int i = 0; i < n; i++) {
		av[To_index(a[i])]++;
		bv[To_index(b[i])]++;
	}

	ans += chk();

	for (int i = n; i < m; i++) {
		bv[To_index(b[i])]++;
		bv[To_index(b[i - n])]--;
		ans += chk();
	}

	cout << ans;
}