백준 14370: 전화번호 수수께끼(Large)

https://www.acmicpc.net/problem/14370

 

 

이번엔 재밌는 문제를 해결해보자.

 

이 문제를 읽고나면 처음 떠올리는 해결책은 브루트포스이다. 하지만, S의 길이가 3 이상 2000 이하이므로 이 문제의 해결책은 아니다. 정확히는 

https://www.acmicpc.net/problem/14369

백준 14369: 전화번호 수수께끼(Small)의 정답에 가깝다.

다만, 이 문제의 해결책으로도 14369 또한 해결할 수 있다!

 

이 문제를 읽었을 때, 나는 머리가 순간 백지가 되었다. 도대체 어떻게 이 문제를 해결해야 할 지 감이 전혀 잡히지 않았었다. 그렇지만, 마음을 다잡고 숫자의 영어들을 쭉 살피었고, 알아낸 것이 하나 있었다. 0~9의 영어 숫자 중에 유일한 알파벳을 가지는 숫자가 있다는 것이다!. 처음 발견한 것은 6이였는데, SIX를 보자 느낌이 오기 시작했다. "X를 가진 영어 숫자는 SIX 밖에 없네? 그럼 혹시 다른 영단어 숫자도?" 란 생각으로 단어들을 늘여놓았다.

• ZERO - 0
• ONE - 1
• TWO - 2
• THREE - 3
• FOUR - 4
• FIVE - 5
• SIX - 6
• SEVEN - 7
• EIGHT - 8
• NINE - 9

이제 유일한 알파벳을 가진 영단어 숫자를 찾았다. 그 결과 ZERO, TWO, FOUR, EIGHT, SIX는 각각 Z, W, U, G, X 를 해당 단어에서 유일하게 가졌다. 그 말은 즉, 입력 전화번호를 카운트 했을 때, 각 키가 되는 알파벳 갯수를 세면 숫자의 갯수 또한 구할 수 있다는 것이다!

• ZERO - Z의 갯수
• ONE 
• TWO - W의 갯수
• THREE
• FOUR - U의 갯수
• FIVE
• SIX - X의 갯수
• SEVEN
• EIGHT - G의 갯수
• NINE

이제 나머지는 어떻게 구할까?

위에서 갯수를 구한 영단어를 빼고 생각을 하면 답은 금방 나왔다.

• ONE
• THREE
• FIVE
• SEVEN
• NINE

이제 유일한 알파벳을 가진 영단어가 생겼다. 이 리스트에서 ONE, THREE, FIVE, SEVEN가 각각 O, (H or R or T), F, S를 유일한 알파벳을 가지고 있다. 또 영단어를 지우면 NINE만이 남고, 이것으로 영단어 갯수를 전부 구할 수 있다!

 

따라서 다음의 순서를 지켜서 알파벳을 카운팅해서 문자열에 넣고, 오름차순으로 정렬을 하면 답이다.

1. ZERO, TWO, FOUR, SIX, EIGHT
2. ONE, THREE, FIVE, SEVEN
3. NINE

#include <iostream>
#include <algorithm>
using namespace std;
int alp[26], T;
string S;

int id(char ch)
{
	return ch - 'A';
}
void solve(string& ans, char key, string word, char num)
{
	if (alp[id(key)] > 0)
	{
		int cnt = alp[id(key)];
		for (int i = 0; i < word.size(); i++)
			alp[id(word[i])] -= cnt;
		while (cnt--) ans.push_back(num);
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> T;
	for (int t = 1; t <= T; t++)
	{
		cin >> S;
		string ans = "";
		for (int i = 0; i < S.size(); i++) ++alp[id(S[i])];
		solve(ans, 'U', "FOUR", '4');
		solve(ans, 'X', "SIX", '6');
		solve(ans, 'Z', "ZERO", '0');
		solve(ans, 'W', "TWO", '2');
		solve(ans, 'G', "EIGHT", '8');
		solve(ans, 'F', "FIVE", '5');
		solve(ans, 'R', "THREE", '3');
		solve(ans, 'O', "ONE", '1');
		solve(ans, 'S', "SEVEN", '7');
		solve(ans, 'I', "NINE", '9');
		sort(ans.begin(), ans.end());
		cout << "Case #"<< t << ": " << ans << '\n';
	}
}

막혔을 때는 더 관찰을 해보는 습관을 가져보자