[종만북 문제] 팬미팅 (문제 ID : FANMEETING, 난이도 : 상)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. 무식하게 풀면, 시간 복잡도가 O(N^2) 가 되어 시간초과가 발생한다.

2. 카라츠바의 알고리즘을 사용해 보자!

---

[종만북 문제] 팬미팅 (문제 ID : FANMEETING, 난이도 : 상)

팬미팅 문제는 종만북에서 처음으로 나오는 '상' 난이도의 문제이다.

하지만 걱정하지 마라. 손은 눈보다 빠르니까... 

근데 사실 손이 빠른 건 별로 도움이 안된다.

 

어쨌든, 이 문제는 '무식하게' 푼다고 하면 O(N^2) 로 풀어볼 수도 있을 것이다. 예시 코드는 아래와 같다(시간초과 함에 유의).

#include <iostream>
#include "stdlib.h"
#include <cmath>
#include <vector>
#include <unordered_set>

using namespace std;

/****************************************************************************************************/
/****************************************************************************************************/
/****************************************************************************************************/

int M;
int N;
vector<char> members;
vector<char> fans;

bool shake(char m, char f)
{
   if (m == 'M' && f == 'M')
      return true;
   return false;
}

void sol()
{
   // 각 멤버별로 팬과 비교를 한다고 할때, 
   // validOffset 에 해당 항목이 없으면 다음 차시에는 Skip 할 수 있다.
   // 즉, validOffset 의 각 항목은 '번째' 를 의미한다
   unordered_set<int> validOffset;
   for (int i = 0; i <= N - M; ++i)
      validOffset.insert(i);

   for (int i = 0; i < M; ++i)
   {
      vector<int> shakes;
      for (int offset : validOffset)
      {
         if (shake(members[i], fans[i + offset]))
            shakes.push_back(offset);
      }

      for (int shk : shakes)
         validOffset.erase(shk);
   }

   cout << validOffset.size() << endl;
}

void inputHandler()
{
   string member;
   string fan;
   
   cin >> member;
   cin >> fan;

   M = member.size();
   N = fan.size();

   members.resize(M);
   fans.resize(N);

   for (int i = 0; i < M; ++i)
      members[i] = member[i];

   for (int i = 0; i < N; ++i)
      fans[i] = fan[i];
}

int main()
{
   int cases;
   cin >> cases;
   while (cases--)
   {
      inputHandler();

      sol();
   }

   return 0;
}

나름대로 최적화를 한다고 해 봐도, 결국 최악의 경우에는 O(N^2) 이 그대로 나오게 된다...

 

그렇다면 이 문제를 어떻게 효율적으로 해결할 수 있을까?

이 문제는 사실 아래처럼, 멤버와 팬의 곱셈으로 이해할 수도 있다.

A 를 멤버, B 를 팬, C 를 멤버와 팬이 포옹할지 말지에 대한 값이라고 하면 이해가 될 것이다.

남자일 때의 값을 1, 여자일 때의 값을 0 이라고 하면... 둘의 곱셈이 0 이 될 때에만 포옹을 한다고 이해할 수 있다!

즉, 우리는 이 어마무시한 길이의 곱셈을 카라츠바 알고리즘을 이용해서 풀면, 시간초과를 회피할 수 있다.

 

그런데... 

카라츠바 알고리즘은 또 뭘까? 위키피디아를 보면, 그 내용이 명확히 나와 있다.

대충 효율성은 아래와 같다. 귀찮아서 대충 때우는 게 아니다. 🤥

 

자, 그럼 카라츠바 알고리즘을 이용해서 이 문제를 풀어보자. 자세한 설명은 주석으로 달아 두었다. 😄

#include <iostream>
#include "stdlib.h"
#include <cmath>
#include <vector>
#include <unordered_set>

using namespace std;

/****************************************************************************************************/
/****************************************************************************************************/
/****************************************************************************************************/

// a += b * (10^k) 를 구현. 자릿수는 처음이 제일 작은 자리수
void addTo(vector<int>& a, const vector<int>& b, int k)
{
	int an = a.size(), bn = b.size();
	a.resize(max(an, bn + k));
	for (int i = 0; i < bn; ++i)
		a[i + k] += b[i];
}

// a -= b 를 구현. a >= b 를 가정
void subFrom(vector<int>& a, const vector<int>& b)
{
	int an = a.size(), bn = b.size();
	a.resize(max(an, bn + 1));
	for (int i = 0; i < bn; ++i) 
		a[i] -= b[i];
}

vector<int> multiply(const vector<int>& a, const vector<int>& b)
{
	int an = a.size(), bn = b.size();
	vector<int> ret(an + bn + 1, 0);
	for (int i = 0; i < an; ++i) 
		for (int j = 0; j < bn; ++j) 
			ret[i + j] += (a[i] * b[j]);

	return ret;
}


// 두 긴 정수의 곱을 반환
vector<int> karatsuba(const vector<int>& a, const vector<int>& b)
{
	int an = a.size(), bn = b.size();

	// a 가 b 보다 짧을 경우 둘을 바꾼다
	if (an < bn)
		return karatsuba(b, a);

	// 기저 사례 : a 나 b 가 비어 있는 경우
	if (an == 0 || bn == 0)
		return vector<int>();

	// 기저 사례 : a 가 비교적 짧은 경우 O(n^2) 곱셈으로 변경. 여기선 생략
	if (an <= 50) 
		return multiply(a, b);

	int half = an / 2;

	// a 와 b 를 밑에서 half 자리와 나머지로 분리
	vector<int> a0(a.begin(), a.begin() + half);
	vector<int> a1(a.begin() + half, a.end());
	vector<int> b0(b.begin(), b.begin() + min(bn, half));
	vector<int> b1(b.begin() + min(bn, half), b.end());

	// z2 = a1 * b1
	vector<int> z2 = karatsuba(a1, b1);

	// z0 = a0 * b0
	vector<int> z0 = karatsuba(a0, b0);

	// a0 = a0 + a1; b0 = b0 + b1
	addTo(a0, a1, 0); addTo(b0, b1, 0);

	// z1 = (a0 * b0) - z0 -z2;
	vector<int> z1 = karatsuba(a0, b0);

	subFrom(z1, z0);
	subFrom(z1, z2);

	// ret = z0 + z1 * 10^half + z2 * 10^(half*2)
	vector<int> ret;
	addTo(ret, z0, 0);
	addTo(ret, z1, half);
	addTo(ret, z2, half + half);

	return ret;
}

int hugs(const string& members, const string& fans)
{
	int N = members.size(), M = fans.size();
	vector<int> A(N), B(M);
	for (int i = 0; i < N; i++) {
		A[i] = (members[i] == 'M');
	}
	for (int i = 0; i < M; i++) {
		B[M - i - 1] = (fans[i] == 'M');
	}

	int ret = 0;

	vector<int> C = karatsuba(B, A);
	for (int i = N - 1; i < M; i++) 
		if (C[i] == 0) 
			ret++;

	return ret;
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		string members, fans;
		cin >> members >> fans;
		cout << hugs(members, fans) << endl;
	}

	return 0;
}