[C++] 백준 8933번: MCS

문제 링크

8933번: MCS

문제 요약

{A, G, T, C}의 개수가 동일한 문자열을 합성적으로 같은 문자열이라고 한다. 문자열이 주어질 때, 이 문자열에서 길이가 k인 부분 문자열들이 존재한다. 이 부분 문자열들 중에 합성적으로 같은 문자열이 가장 많은 것을 k-MCS라고 한다. 이때 k-MCS의 등장횟수를 구해야 한다.

접근 방법

맵을 사용하는 기본문제 격의 문제였습니다.

1. 윈도우를 이동시키면서 윈도우 내의 A, G, T, C의 수를 세어 줍니다.
2. 매 반복마다 A, G, T, C의 개수를 key로 삼아 맵에서 찾아줍니다. 만약 존재하지 않는다면 value를 1로하여 추가해주고, 존재한다면 1 증가시켜 줍니다.
3. 윈도우를 끝까지 이동시키면 맵의 처음부터 이동하면서 최댓값을 찾습니다.

쉬운 문제이긴 했지만 제 경우에는 트리맵을 사용했고, 구조체를 key로 쓰면서 코드가 조금 길게 나온거 같기는 합니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Info {
	int a, g, c, t;

	bool operator<(const Info& info) const
	{
		if (a == info.a)
		{
			if(g == info.g)
			{
				if (c == info.c)
					return t < info.t;
				return c < info.c;
			}
			return g < info.g;
		}
		return a < info.a;
	}
};

map<Info, int> m;

int func(char c)
{
	switch (c)
	{
	case 'A':
		return 0;
	case 'G':
		return 1;
	case 'C':
		return 2;
	case 'T':
		return 3;
	}
}

void add(vector<int>& v)
{
	if (m.find({ v[0], v[1], v[2], v[3] }) == m.end())
		m.insert({ { v[0], v[1], v[2], v[3] }, 1 });
	else
		m[{v[0], v[1], v[2], v[3]}]++;
}

int main(void)
{
	int t;
	cin >> t;

	while (t--)
	{
		int k;
		string str;
		cin >> k >> str;

		vector<int> v(4, 0);
		for (int i = 0; i < k; i++)
			v[func(str[i])]++;

		add(v);
		for (int i = k; i < str.size(); i++)
		{
			v[func(str[i])]++;
			v[func(str[i - k])]--;
			add(v);
		}

		int res = 0;
		for (map<Info, int>::iterator it = m.begin(); it != m.end(); it++)
			res = max(res, it->second);
		cout << res << '\n';
		m.clear();
	}

	return 0;
}