알고리즘 문제해결 전략 Chapter 20 - NAMING(C++)

포타토·2020년 1월 1일
0

알고리즘

목록 보기
14/76

예제: 접두사/접미사

문제
아주대에 사는 외수는 작명에 능하기로 유명해서 많은 부부들이 아주대로 몰려와서 태어나는 아이들의 이름을 지어달라고 한다. 부부들은 이름은 잘 짓는게 출세에 영향을 미친다고 생각을 하고 있으며, 따라서 좋은 이름을 지어 출세하기를 기원한다. 허나 게으른 외수에게 작명은 지루한 작업이다. 효율적으로 일을 하고자 궁리하던 차에 쉽지만 기가 막힌 알고리즘을 고안하게 되었다.

외수가 개발한 작명 알고리즘은 다음과 같다.

아버지의 이름 뒤에 어머니의 이름을 덧붙여서 하나의 새로운 문자열 S로 만든다.
이 문자열 S의 접두사(prefix)도 되고 접미사(suffix)도 되는 문자열을 찾는다.
예를 들어 아버지의 이름이 'ala'고 어머니의 이름이 'la' 일 경우 S = 'ala' + 'la' = alala다. 그리고 이 문자열의 접두사이기도 하고 접미사이기도 한 문자열은 다음 세가지다.

  • a
  • ala
  • alala

아버지와 어머니의 이름이 주어질 때, 외수의 규칙을 이용해 지어줄 수 있는 이름들을 모두 찾는 프로그램을 작성하라. 문제에서는 편의상 모든 문자열 대신, 가능한 모든 문자열의 길이를 찾는다.

입력
빈칸이 없는 영문 알파벳 소문자로 이뤄진 문자열이 입력이 두 줄 입력된다.
첫 번째 줄은 아버지의 이름이고, 두 번째 줄은 어머니의 이름이다.
두 문자열의 길이를 합쳐서 400,000 자가 넘어가는 입력은 들어오지 않는다.

출력
외수가 주어질 수 있는 이름들의 길이들을 한 줄에 출력한다.
출력되는 숫자 사이에는 정확히 공백이 하나 포함되어야 하며, 길이는 오름차순으로 출력되어야 한다.

예제 입력

ababcabababa
bcabab

예제 출력

2 4 9 18

풀이

KMP 알고리즘?

사실 이 문제는 반복문을 무지하게 돌리면 비교적 쉬운 로직으로 답을 찾을 수 있을 것이다. 그러나 시간이 어마어마하게 걸릴 것이다.

그래서, 알고리즘 문제해결 전략에서는 KMP(Knuthh-Morris-Pratt) 알고리즘을 제시한다. KMP 알고리즘이란 문자열 검색 최적화 알고리즘이다. 구현 코드 자체가 복잡하지 않으나, 알고리즘을 이해하기가 꽤나 어려웠다. 지금도 확실히 이해하지는 못하는 것 같다. 얼른 내껄로 만들어야지..

따라서, 이 문제는 오직 KMP 알고리즘을 이용하는 문제로 보면 된다. KMP 알고리즘에 대해 다루면 포스팅이 너무 길어지므로, 기회가 되면 다뤄보도록 하겠다. 우선 나부터 확실히 이해하고..

전체적인 소스코드는 아래와 같다.

소스 코드

#include<iostream>
#include<string>
#include<vector>

using namespace std;

vector<int> setPartialMatch(const string& word) {
	int m = word.size();
	vector<int> pi(m, 0);

	int begin = 1, matched = 0;

	while (begin + matched < m) {
		if (word[begin + matched] == word[matched]) {
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else {
			if (matched == 0) begin++;
			else {
				begin += (matched - pi[matched - 1]);
				matched = pi[matched - 1];
			}
		}
	}

	return pi;
}

vector<int> namingCnt(const string& word) {
	
	vector<int> res, pi;
	pi = setPartialMatch(word);

	int k = pi.size();

	while (k > 0) {
		res.push_back(k);
		k = pi[k - 1];
	}

	return res;
}

int main() {

	string dad, mom;
	cin >> dad >> mom;

	vector<int> res = namingCnt(dad + mom);

	for (int i = res.size() - 1; i >= 0; i--) {
		cout << res[i] << " ";
	}
	cout << endl;

	return 0;
}

풀이 후기

KMP 알고리즘의 구현 자체는 크게 어려운 것이 아니어서 이 문제를 풀었지만, 알고리즘을 이해하는 것은 어려웠다. 지금도 확실히 이해하지는 못하는걸로 보아, 응용문제가 나온다면 쩔쩔맬 가능성이 크다. 틈틈이 공부해서 내껄로 만들어야겠다.

profile
개발자 성장일기

0개의 댓글