언제나 처음처럼

[문제 링크]

입력으로 주어지는 문자열 H와 H의 모든 부분문자열 N에 대해 KMP-search 를 수행하여 H에 N과 일치하는 문자열이 2개 이상 존재하는 N 중에서 길이가 가장 긴 부분문자열의 길이를 출력해주면 된다.

다만, 부분문자열 N의 길이를 1에서부터 시작하면 시간이 너무 오래걸리므로, 이분탐색을 활용하여 시간복잡도를 줄였다. (그래도 오래 걸리는건 함정;;)

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

vector<int> getPartialMatch(string& N) {
	int Nlen = N.length();
	vector<int> pi(Nlen, 0);

	int begin = 1, matched = 0;
	while (begin + matched < Nlen) {
		if (N[begin + matched] == N[matched]) {
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else {
			if (matched == 0)
				begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return pi;
}
bool KMP_search(string& H, string& N) {
	int Hlen = H.length(), Nlen = N.length();
	vector<int> pi = getPartialMatch(N);
	int cnt = 0;

	int begin = 0, matched = 0;
	while (begin <= Hlen - Nlen) {
		if (matched < Nlen && H[begin + matched] == N[matched]) {
			matched++;
			if (matched == Nlen) {
				cnt++;
				if (cnt == 2) return true;
			}
		}
		else {
			if (matched == 0)
				begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return false;
}

int allPartialStrSearch(string str) {
	int ret = 0;
	int len = str.length();

	int start = 1, end = len;

	while (start <= end) {
		int mid = (start + end) / 2;
		if (mid == 0) break;

		for (int i = 0; i + mid <= len; i++) {
			string N = str.substr(i, mid);
			if (KMP_search(str, N)) {
				ret = mid;
				start = mid + 1;
				break;
			}
		}
		if (start != mid + 1)
			end = mid - 1;
	}

	return ret;
}

int main(void) {
	string str;
	cin >> str;

	cout << allPartialStrSearch(str) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 165 day

[문제 링크]

분할정복과 이분탐색이 섞인 문제인거같다. 이분탐색 풀이법이 생각나지 않아 다른사람들의 풀이법을 참고하였다. 3일 후에 다시한번 풀어봐야 겠다.

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

vector<int> dayMoney;
int N, M, sum;

bool Solution(int money)
{
	int temp = money, withdraw = 1;
	for (int i = 0; i < N; i++)
	{
		if (dayMoney[i] > money)
			return false;
		if (temp - dayMoney[i] < 0)
		{
			temp = money;
			withdraw++;
		}
		temp -= dayMoney[i];
	}
	return M >= withdraw;
}
int main(void)
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		int n;
		cin >> n;
		dayMoney.push_back(n);
		sum += n;
	}

	// binary_search //
	int start = 1, end = sum; // sum은 M이 1인 모든 금액을 더한 값
	int result;
	while (start <= end)
	{
		int mid = (start + end) / 2;
		if (Solution(mid))	// 인출횟수가 M보다 작거나 같음 -> 인출금을 줄여보자
		{
			result = mid;
			end = mid -1;
		}
		else
			start = mid + 1;
	}
	cout << result << endl;
	return 0;
}

알고리즘 200일 프로젝트 - 39day