[boj : 2020] 부분 염기서열

www.acmicpc.net/problem/2020

2020번: 부분 염기서열

문제 : 문자열이 주어지고 동일한 부분 문자열의 빈도가 m 이상일때 조건에 맞게 정렬해라. 그리고 k 번째 문자열을 출력해라.

 

해설: 너무 어려움,,,혼자 힘으로 못풀었습니다.(메모리 제한 때문에 ㅠㅠ)

해결 과정은 BFS를 푸는 것 처럼 풀 수 있습니다.

1)입력 문자열(str)의 각 문자를 동일한 문자끼리 모읍니다.(map<char,vector<int>>)

2)그리고 나서 큐를 선언하고 vector를 push 해줍니다.

3)이 큐에서 하나씩 뺄때 만약 m 보다 작다면 그냥 continue로 아무 동작도 해주지 않습니다.

(만약,뽑아낸 n길이의 문자열의 빈도수가 m 보다 작다면 이 n 길이의 문자열 중 최소 하나의 문자는 m 보다 작기 때문에 절대 현재 뽑아낸 n길이의 문자열은 존재할 수가 없게 되는 것 입니다.) 

4)만약 m 보다 크다면 뽑아낸 문자열의 다음 index에 해당되는 문자를 추가하여 새롭게 선언한 map<char,vector<int>>에 삽입해 줍니다. 그리고 다시 큐에 vector를 push 해 줍니다.

5)k번째로 뽑아낸 문자열을 저장해 주고 마무리 출력을 해주면 됩니다.

 

//뭔 멍멍이 소리를 하는 건가 싶으실 텐데 그냥 코드를 보면서 하나하나 따라가시는게 더 나을 듯 싶습니다.

 

//thank u "djm03178"

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<queue>

using namespace std;

vector<pair<int, int>> v;

int main()
{
	int n, m, k;
	string str;

	int ans = 0;
	string ans2;

	cin >> n >> m >> k >> str;

	int len = 1;
	queue<vector<int>> q;
	map<char, vector<int>> mp;

	for (int i = 0; i < str.length(); i++)
		mp[str[i]].push_back(i);
	for (auto u = mp.begin(); u != mp.end(); u++)
		q.push(u->second);	

	while (!q.empty())
	{
		int size = q.size();
		for (int s = 0; s<size; s++) {
			auto cur = q.front();
			q.pop();
			
			if ((int)cur.size() < m)continue;
			
			ans++;
			if (ans==k) 
				ans2 = str.substr(cur[0], len);
			
			map<char, vector<int>> mp2;
			for (int x : cur) {
				if (x + len >= n)break;
				mp2[str[x + len]].push_back(x);
			}
			for (auto u = mp2.begin(); u != mp2.end(); u++)
				q.push(u->second);
		}
		len++;
	}
	cout << ans << "\n" << ans2;
	return 0;
}