[G5] 백준 20437번 문자열 게임 2 C++ 해시맵, 문자열

리뷰

 

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

이분탐색 + 슬라이딩 윈도우로 3번은 구현 했으나, 4번에 대한 아이디어가 떠오르지 않았다.

결국 질문게시판을 보고 해시맵으로 구현하여 AC를 맞았다 ㅠㅠ

 

전역 변수

• t : 주어지는 테스트 케이스의 개수
• n, k : 입력 받은 문자열의 길이를 저장할 변수 n, 부분 문자열에서 정확히 문자를 포함해야 하는 개수 k
• w : 입력 받은 문자열을 저장할 문자열 변수
• dic : 문자열에서의 단어 정보를 저장할 맵, key는 char, value는 vector<int> 타입이다.

 

함수

없음

 

 

문제풀이

1. t를 입력 받고, 테스트 케이스의 개수만큼 반복문을 수행해 준다.
2. 이전 테케에서 사용한 dic정보를 초기화 해주고 w, k를 입력받아 준다.
3. n을 w의 size로 초기화 해주고, case1, case2를 각각 매우 큰 값과 작은 값으로 초기화 해준다.
4. 문자열을 순회하며 각 알파벳을 key로 하는 dic의 vector에 인덱스를 추가해 준다.
5. dic을 순회하며 key는 key로, value는 value로 초기화 해준 다음 변수 m에 vector의 size를 넣어준다.
6. 만약 m이 k보다 작다면 성립하지 않으므로 continue처리해 준다.
7. m - k번의 반복문을 수행하고, 각 k번의 구간 인덱스를 case1, case2에 최소 최대값으로 갱신해 준다.
8. 만약 case1이나 case2에 값이 할당되지 않았다면 -1을, 아니라면 각각을 출력해 준다.
9. 위 작업을 테스트케이스 마다 매번 반복해 준다.

 

참고 사항

1. 알파벳 소문자로 이루어진 문자열 W가 주어진다.
2. 양의 정수 K가 주어진다.
3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

3, 4번 모두 부분문자열의 첫 번째와 마지막 글자가 동일할 때가 최적해에 해당한다.

 

 

정답 코드

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;

int t, n, k;
string w;
unordered_map<char, vector<int>> dic;

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

	cin >> t;
	while (t--) {
		dic.clear();
		cin >> w >> k;
		n = w.size();
		
		int case1 = 1e9, case2 = 0;
		for (int i = 0; i < n; i++) dic[w[i]].push_back(i);
		for (auto d : dic) {
			int key = d.first;
			vector<int> val = d.second;
			int m = val.size();
			if (m < k) continue;
			for (int i = 0; i <= m - k; i++) {
				case1 = min(case1, val[i + k - 1] - val[i] + 1);
				case2 = max(case2, val[i + k - 1] - val[i] + 1);
			}
		}
		if (case1 == 1e9 || !case2) cout << -1 << "\n";
		else cout << case1 << " " << case2 << "\n";
	}
}