Boj 2848) 알고스팟어

문제

백준 2848

설명

먼저 들어오는 모든 알파벳을 체크하고, 연속된 문자열 간의 공통 prefix 를 구해서 바로 그 다음문자를 기준으로 대소관계를 넣었다. 이때 두 문자가 사전순이 불가능한 경우가 하나 있는데, 앞의 문자가 뒤의 문자보다 더 길면서 common prefix 가 뒤의 문자와 같은 경우이다. 이를 생각할 수 있느냐 없느냐로 문제푸는 시간이 확 달라지게 된다.

시간 복잡도

O(\(26^2\))

코드

vector<int> srcs[26];
int n_targets[26];
char matrix[26][26];
bool visits[26]; int n_alp = 0;

// 모든 문자열 종류를 기록함
inline void Regist(string& in)
{
	for (auto a : in) 
		if (!visits[a - 'a']) { 
			visits[a - 'a'] = true; 
			n_alp++; 
		}
}

int main()
{
	fastio;
	
	bool contra = false;
	string prev, cur; 
    
	int n; cin >> n;
	cin >> cur; Regist(cur);
	for (int i = 1; i < n; i++)
	{
		prev = cur; cin >> cur; Regist(cur);

		int prefix = -1;
		int min_size = min(prev.size(), cur.size());

		while (prefix + 1 < min_size && prev[prefix + 1] == cur[prefix + 1]) prefix++;

		// aa, a 의 경우
		if (prefix == cur.size() - 1 && prev.size() > cur.size())
		{
			contra = true;
			break;
		}

		if (prefix + 1 < min_size)
		{
			int si = prev[prefix + 1] - 'a', ei = cur[prefix + 1] - 'a';
			if (matrix[si][ei] != 0 && matrix[si][ei] != '>') {
				contra = true;
				break;
			}
			matrix[si][ei] = '>';
			matrix[ei][si] = '<';
		}
	}

	if (contra) {
		cout << "!";
		return 0;
	}

	for (int i = 0; i < 26; i++)
		for (int j = i + 1; j < 26; j++)
		{
			int w = i, l = j;
			if (matrix[i][j] == 0) continue;
			if (matrix[i][j] == '<') swap(w, l);
			srcs[w].push_back(l);
			n_targets[l]++;
		}

	queue<int> q;
	for (int i = 0; i < 26; i++)
		if (visits[i] && n_targets[i] == 0) q.push(i);

	vector<int> ans; bool bAmbig = false;
	while (!q.empty())
	{
		// 한번에 여러 갈래로 나뉘면 모호한 경우
		if (q.size() > 1) {
			bAmbig = true;
			break;
		}
		int cur = q.front(); q.pop();
		ans.push_back(cur);
		for (int i = 0; i < 26; i++)
			if (matrix[cur][i] == '>' && i != cur)
				if (--n_targets[i] <= 0)
					q.push(i);
	}

	if (bAmbig) cout << "?";
	else if (ans.size() != n_alp) cout << "!";
	else for (auto a : ans) cout << char(a + 'a');
}