문제

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다.
효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.

예를 들어, 학습된 단어들이 아래와 같을 때

go
gone
guild

• go를 찾을 때 go를 모두 입력해야 한다.
• gone을 찾을 때 gon 까지 입력해야 한다. (gon이 입력되기 전까지는 go 인지 gone인지 확신할 수 없다.)
• guild를 찾을 때는 gu 까지만 입력하면 guild가 완성된다.

이 경우 총 입력해야 할 문자의 수는 7이다.

라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.

입력

학습과 검색에 사용될 중복 없는 단어 N개가 주어진다.
모든 단어는 알파벳 소문자로 구성되며 단어의 수 N과 단어들의 길이의 총합 L의 범위는 다음과 같다.

• 2 <= N <= 100,000
• 2 <= L <= 1,000,000

출력

단어를 찾을 때 입력해야 할 총 문자수를 리턴한다.

풀이

포털사이트에서 검색할 때 자동완성 기능이 있는 것은 누구나 다 안다. 이 문제는 그에 대한 문제이다.
처음엔 입력받은 벡터문자열을 정렬하여 한글자씩 비교해가며 카운트를 세려고 했는데.. 시간복잡도를 배우면서 엄청 비효율적이 알고리즘이라는 것을 깨달았다.
그러다가 구글링 중 https://hwan-shell.tistory.com/133 블로그에서 Tri구조라는 것을 보았고, 이 알고리즘은 이 문제를 위해 생겨났다고 생각했을 정도로 문자열 처리에 특화되었다.
카카오 문제 예제중 첫번째 예제에서 guide를 추가해서 어떤 알고리즘인지 보자.

모든 단어에 g는 공통으로 포함되어 있다. 이에 따라 g가 루트노드가 된다.
두번째 글자에서부터 분리된다. go, gone는 o가 공통이고, guide,guild는 u가 공통이다. 다음 세번째 글자에서부턴 go는 끝났고 나머지 세글자에서 이전 과정처럼 계속 분리해나가면 된다.
그래서 최종적으로 분리된 모델이 위 그림이다.
그럼 이 알고리즘을 카카오 문제에 적용시키면 아래 그림과 같다. (아주 간략하게 그려봤다.)

Tri구조 내에 글자를 담을 노드와, 각 글자가 몇번 입력되었는지 보관할 count 배열을 생성한다. 배열의 크기는 알파벳 개수, 26개로 지정한다.
여기서 주의할 점은 Tri구조 배열을 포인터로 생성해야 한다. 맨 처음엔 이해를 못했는데 알고리즘 메커니즘을 살펴보니 알겠더라.
포인터 배열의 각 인덱스에선 다음 노드의 주소를 가리켜야 하기 때문이었다.

그럼 다시 알고리즘에 첫번째 예제를 넣으면?

• go는 다 입력해야 하므로 2
• gone는 n까지 입력하면 되므로 3
• guild는 gu까지 입력해야 하므로 2

따라서 결과는 7이다.

코드

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

using namespace std;
const int ALP = 26;

class triNode {
private:
	triNode* child[ALP];
	int count[26] = { 0, };
public:
	triNode() {							// 생성자, 처음은 주소를 NULL값으로 지정
		for (int i = 0; i < ALP; i++)
			child[i] = NULL;
	}
	~triNode() {						//소멸자, 동적할당 해제
		for (int i = 0; i < ALP; i++)
			delete child[i];			// 단일 객체에 대해서 해제하는것이기 때문에, delete[]가 아닌 delete이다.
	}
	void insert(const char* str) {		//입력받은 문자열의 각각문자를 Tri구조에 학습.
		if (!*str)
			return;
		int next = *str - 'a';			// 배열의 인덱스를 가리키기 위해 integer로 변환
		count[next]++;					// 해다 문자가 입력됬으니 +1해준다.
		if (!child[next])
			child[next] = new triNode();	// 만약 노드가 NULL이라면 처음입력받은 문자이므로 다음 노드를 동적할당 해준다.
		child[next]->insert(str + 1);		// 다음 문자를 insert한다.
	}

	int find(const char* str, int n) {		// 정답을 찾기 위한 과정
		if (!(*str))
			return (n - 1);					// 문자열 끝까지 왔다면, 입력받은 변수 n-1을 반환.
		int cnt = *str - 'a';
		if (count[cnt] == 1)				// count[cnt] == 1이라는 것은 해당 문자가 전체 통틀어서 한번밖에 입력받지 못했다는 것이고, 이는 유일한 문자이므로 이 문자까지만 입력하면 자동완성이 된다.
			return n;
		return child[cnt]->find(str + 1, n + 1); // count가 2 이상이라면 다음 문자와 입력한 문자 개수 n+1을 입력하여 find로 재귀해준다.
	}
};

int solution(vector<string> words) {
	int answer = 0;
	triNode tri;

	for (int i = 0; i < words.size(); i++) {
		tri.insert(words[i].c_str());
	}
	for (int i = 0; i < words.size(); i++)
		answer += tri.find(words[i].c_str(), 1);
	return answer;
}

int main() {
	vector <string> v = { "go", "gone", "guild" };
	int n = solution(v);
	cout << n;
	return (0);
}