[백준 1305][💚5] 광고 (KMP)

🚀 난이도

💚 플래티넘 5

🚀 문제

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

🚀 내 풀이 ⭕

📌 KMP 알고리즘 에 대한 자세한 설명은 링크로 https://ansohxxn.github.io/algorithm/kmp/

이 문제는 KMP 알고리즘의 실패 함수로 해결할 수 있다. 위 링크에 실패 함수 코드에 대한 설명도 자세히 기재해두었으니 참고했으면 좋겠다. :)

---

어느 순간 전광판을 딱 쳐다봤을 때 “그때의 문자열에서 가능한” 광고 길이를 찾아내는 것이기 때문에 실제 광고 길이가 어떤지는 중요치 않다. 실제 광고 길이를 알아내기 위한 문제가 아니다. 그냥 딱 그 순간에 본! 입력으로 주어지는 그 문자열에서 “가능한” 광고 길이를 찾는 문제이다.

문제에서 설명한 예시인 “aabaaa” 라는 문자열에서 가능한 광고 길이 중 가장 짧은 것을 알아내보도록 하자. 광고판의 크기는 6 이라는 것을 알고 있기 때문에 “aabaaa” 문자열, 즉 어느 순간 전광판을 봤을 때의 문자열의 접미사는 곧 광고의 접두사여야 한다. 왜냐하면 이 광고는 한 칸씩 옆으로 이동하기 때문이다. “aabaaa” 문자열의 접미사 “aa” 는 광고 “aaba”의 접두사인 “aa” 이기도 하다. 즉, (광고 + 광고의 접미사) 형태로 전광판의 남은 부분을 광고의 접미사로 채우게 된다.

내가 헷갈려서.. ㅠㅠㅋㅋ 다시 한번 더 언급하지만 문제에서 입력으로 주어지는 어느 순간 전광판을 딱 쳐다봤을 때 “그때의 문자열에서 가능한” 광고 길이를 찾아내는 것이지 실제 광고가 무엇이냐를 알아내는게 아니다. 그러므로 주어진 문자열이 (광고 + 광고의 접미사) 형태 로 생각해볼 수 있다는 것에만 주목하고 전광판 문자열의 접두사와 접미사가 같은 최대 길이를 구하면 된다. 즉, 실패함수를 구하는 것과도 같다. 최대 길이를 구해야 하는 이유는, 접미사는 전광판에서 광고로 채우고 남은 부분을 채우기 때문에 접미사가 최대한 길어야지만 “가능한” 광고 길이가 짧아지기 때문이다.

전광판 길이에서 접두사와 접미사가 같은 최대 길이를 구하는 것이기에 1️⃣ 실패함수 테이블을 전처리로 구한 후, 2️⃣ \(L - pi[L-1]\) 을 답으로 도출하면 된다.

답은 6 글자 광고판 길이의 접두사와 접미사가 같은 최대 길이인 pi[5] 를 광고판 길이 L 에서 빼주면 된다. “aabaaa” 에서 접두사와 접미사가 같은 최대 길이는 “aa” 의 길이인 2 이므로 이를 6 에서 빼주면 된다. 즉, “aabaaa” 에서 가능한 광고의 제일 짧은 길이는 4 인 것이다. “aaba” !!

#include <bits/stdc++.h>

using namespace std;

vector<int> Fail(string pattern) {
	int m = pattern.length();
	vector<int> pi(m); // partial match table

	pi[0] = 0;
	for (int i = 1, j = 0; i < m; i++) { 
		while (j > 0 && pattern[i] != pattern[j])
			j = pi[j - 1]; 
		if (pattern[i] == pattern[j])
			pi[i] = ++j; 
	} 
	return pi;
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int L;
	cin >> L;
	string ad;
	cin >> ad;

	vector<int> pi = Fail(ad);
	cout << L - pi[L - 1];
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기