[BOJ 3080] 아름다운 이름

[문제]

 

www.acmicpc.net/problem/3080

3080번: 아름다운 이름

 

[난이도]

 

- Platinum 2 (solved.ac 20.12.10 기준)

 

 

[필요 개념]

 

- 트라이 (Trie)

- 재귀

- 순열

 

 

[풀이]

 

문제의 조건을 해석해보면, 특정 index에서 묶이는 문자열들이 있다. 

예제 2를 통해서 이해해보자.

 

 

같은 알파벳 순서로 시작하는 두 이름 사이에는 모두 그 순서로 시작하는 단어가 있어야 한다. 

이 말은, 같은 알파벳 순서로 시작하는 이름들은 모두 이웃해야 한다는 의미이다. 

 

예를 들어서 MART로 시작하는 두 단어 MARTA, MARTINA 사이에는 아무런 단어가 오지 못한다. 

그리고 MARTA와 MARTINA의 순서는 바뀌어도 상관이 없다. 

그다음, MAR로 시작하는 단어 사이에는 MATO는 올 수 없다. 

즉, MARICA, MARTA, MARA, MARTINA 네 단어를 배열한 다음에, 양 끝에 MATO를 붙일 수 있는 것이다.

이때, MARTA와 MARTINA가 이미 이웃해 있기 때문에 하나로 묶어줘야 하므로 한 묶음과 MARICA, MARA를 일렬로 나열하는 경우의 수는 3!이다. 

MARTA와 MARTINA의 순서는 바뀌어도 상관없기 때문에 최종적으로 MAR로 시작하는 네 단어를 배열하는 경우의 수는 2*3! = 12가지이다.

마지막으로 MATO는 양 끝에 배정될 수 있기 때문에 총 경우의 수는 24가지로 나오게 된다. 

 

이처럼 문자열의 인덱스를 가장 오른쪽부터 보면서 경우의 수를 계속해서 재귀로 계산해나가면 된다.

문자열들의 탐색은 트라이로 하면 되는데, 이 문제의 메모리 제한이 빡빡해서 메모리 초과가 나지 않게 조심해야 한다. 

(map을 이용해도 MLE가 나서 많이 당황했다...)

 

첫번째 방법으로는 vector를 이용한다.

vector를 이용하면 아슬하게 메모리 제한을 통과한다. 따라서 vector보다 메모리 상수가 더 큰 map을 이용하면 MLE가 나게 된다.

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
int N; 
ll fac[30];
struct Trie {
	vector<pair<char, Trie*>> ch;
	int end;
	Trie() {
		end = false;
	}
	void insert(const char*s) {
		if (!*s) {
			end = true;
			return;
		}
		int now = *s - 'A';
		for (auto p : ch) {
			if (p.first == now) {
				p.second->insert(s + 1);
				return;
			}
		}
		ch.push_back({ now, new Trie });
		ch.back().second->insert(s + 1);
	}
};
Trie *root;
ll sol(Trie * now) {
	int cnt = 0;
	ll res = 1;
	for (auto p : now->ch) {
		res *= sol(p.second);
		res %= MOD;
		cnt++;
	}
	return (res * fac[cnt + (now->end ? 1 : 0)]) % MOD;
}
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N;
	fac[0] = 1;
	for (int i = 1; i <30; i++) {
		fac[i] = (fac[i - 1] * i)%MOD;
	}
	root = new Trie;
	for (int i = 1; i <= N; i++) {
		string s; cin >> s;
		root->insert(s.c_str());
	}
	cout << sol(root);
}

 

두 번째 방법으로는 관찰이 필요하다. 이 블로그를 참고했다. ( devbelly.tistory.com/41 )

 

예를 들어서 ABCDEF와 ABEWQF, AGIWKS라는 세 문자열이 있다고 하자. 이 세 문자열을 나열하기 위해서는 사실 2번째 문자까지만 보면 된다. 즉, AB, AB, AG 세 단어를 나열하는 경우와 동일하게 나온다. 

그러므로 충분히 비교 가능한 만큼의 문자만 트라이에 넣으면 된다. 

같은 알파벳 순서로 시작하는 단어가 몇 개인지가 중요하기 때문에, 문자열 A와 가장 많이 겹치는 문자열을 찾아서 

처음으로 겹치지 않는 지점까지만 잘라서 넣어주면 A는 다른 모든 문자열과 충분히 비교할 수 있다.

 

그렇다면 자르는 지점은 어떻게 찾을 수 있을까?

입력받은 이름들을 모두 정렬하게 되면, A[i]와 prefix가 가장 많이 겹치는 문자열은 A[i-1] 또는 A[i+1]이다. 

따라서, max(lcp(A[i], A[i-1] , lcp(A[i], A[i+1]) + 1 (lcp = length of longest common prefix) 만큼 문자열을 트라이에 넣어주면 된다. 

 

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
int N; 
ll fac[100];
struct Trie {
	map<char, Trie *>ch;
	bool end;
	Trie() {
		end = false;
	}
	void insert(const char *s, int cnt) {
		if (cnt == -1 || !*s) {
			end = true;
			return;
		}
		int now = *s - 'A';
		if (ch.find(now) == ch.end()) ch[now] = new Trie;
		ch[now]->insert(s + 1, cnt-1);
	}
};
Trie *root;
ll sol(Trie * now) {
	int cnt = 0;
	ll res = 1;
	for (int i = 0; i < 26; i++) {
		if (now->ch.find(i) != now->ch.end()) {
			res *= sol(now->ch[i]);
			res %= MOD;
			cnt++;
		}
	}
	return (res * fac[cnt + (now->end ? 1 : 0)]) % MOD;
}
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N;
	fac[0] = 1;
	for (int i = 1; i <100; i++) {
		fac[i] = (fac[i - 1] * i)%MOD;
	}
	root = new Trie;
	vector<string> v;
	for (int i = 1; i <= N; i++) {
		string s; cin >> s;
		v.push_back(s);
	}
	sort(all(v));
	int pre = 0, post = 0;
	for (int i = 0; i < N; i++) {
		if (i == N - 1) {
			root->insert(v[i].c_str(), pre + 1);
		}
		else {
			for (int j = 0; j < sz(v[i]); j++) {
				if (v[i][j] != v[i + 1][j]) {
					break;
				}				
				post = j;
			}
			root->insert(v[i].c_str(), max(pre, post)+1);
			pre = post;
		}
	}
	cout << sol(root);
}

 

 

위의 결과가 vector를 이용한 결과이고, 밑의 결과가 필요한 만큼 문자열을 넣은 결과이다. 

한눈에 봐도 메모리, 시간, 코드 길이에서 둘의 차이가 확실히 나는 것을 알 수 있다.