[Kickstart][2020][Round A] 4. Bundling

문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3ff3

---

Pip는 N개의 문자열을 가지고 있다. 문자열들은 모두 대문자로만 이루어진다.

Pip는 이 문자열들을 그룹화 시키려고 한다. 이 때, 각 그룹은 정확히 K개의 문자열들로 이루어진다.

각 그룹의 점수는 그룹에 속한 문자열들의 공통 prefix 길이다.

만들 수 있는 그룹들의 점수의 합의 최대값은 얼마인가.

---

문자열 배열, 공통된 Prefix.. 트라이를 써야될 것 같은 느낌이 든다.

일단 N개의 문자열들로 Trie를 만든다.

그룹들의 최대값을 만드려면 어떻게 해야하는지 먼저 고민해보자.

최대값을 만드려면 prefix가 커야한다. 즉, 트라이에서 depth가 클수록 큰 점수가 된다.

따라서 depth가 큰 곳부터(아래에서 부터 위로 탐색) K개의 그룹을 만들 수 있으면 score 합에 더한다.

K개의 그룹을 만들 수 없으면 이는 부모 노드에서 처리하게 그룹을 만들고 남은 문자열들의 개수를 위로 올린다.

// node = 탐색 위치
// depth = 트리의 depth, prefix의 길이와 같다.
    
// node를 루트로 하는 서브트리로 ans에 가능한 그룹 점수들을 더하고
// 그룹화 하지 못한 문자열들의 개수는 반환한다.
int solve(int depth, Node* node) {
	int cnt = 현재 노드를 마지막으로 하는 문자열의 갯수;
	for (자식 node들 탐색) {
		Node* next = 자식 노드중하나;
		cnt += solve(depth + 1, next); // 자식 노드들에서 그룹화되지 못한 문자열들의 개수를 더한다.
	}

	// 정답에 서브트리가 가지고 있는 문자열들 중 아직 분류되지 않은 문자열들을 
	// K개씩 분류할 때의 그룹화된 개수(cnt / K) * 각 그룹의 점수(depth)를 정답(ans)에 더한다.
	ans += depth * (cnt / K);
	return hasPrefixStringCnt % K; // K개씩 분류할 때 나머지 = 그룹화되지 못한 문자열들 갯수
}

핵심 로직을 간단히 설명하면 위와 같다. (소스코드 참고)

node는 탐색하는 위치이기 때문에 파라미터로 들고있고, depth는 prefix가 되므로 score로 사용하기 위해 파라미터로 사용한다.

 

시간복잡도는 O(NlogM). Trie를 생성할 때 소요되는 시간이다. 

N = 문자열 갯수. M = 각 문자열 길이

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codejam/kickstart/2020/roundA/4.%20Bundling.cpp