취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14369번 문제인 전화번호 수수께끼 (Small)이다.
문제는 아래 링크를 확인하자.

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

14370번 문제(링크)에서 입력이 작아진 문제이다. 해당 문제의 풀이글을 참고해 문제를 해결하자.

주어지는 문자열의 길이가 짧다는 점을 이용해, 해당 길이보다 작은 길이로 나올 수 있는 모든 경우를 완전탐색으로 미리 찾아두고 문제를 해결할 수도 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int cnt[128];
vector<int> ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	for (int t = 1; t <= T; t++) {
		memset(cnt, 0, sizeof(cnt));
		string s; cin >> s;
		for (auto& l : s) cnt[l]++;
		
		ans.clear();
		while (cnt['W']) {
			ans.emplace_back(2);
			cnt['T']--, cnt['W']--, cnt['O']--;
		}
		while (cnt['U']) {
			ans.emplace_back(4);
			cnt['F']--, cnt['O']--, cnt['U']--, cnt['R']--;
		}
		while (cnt['X']) {
			ans.emplace_back(6);
			cnt['S']--, cnt['I']--, cnt['X']--;
		}
		while (cnt['G']) {
			ans.emplace_back(8);
			cnt['E']--, cnt['I']--, cnt['G']--, cnt['H']--, cnt['T']--;
		}
		while (cnt['Z']) {
			ans.emplace_back(0);
			cnt['Z']--, cnt['E']--, cnt['R']--, cnt['O']--;
		}
		while (cnt['T']) {
			ans.emplace_back(3);
			cnt['T']--, cnt['H']--, cnt['R']--, cnt['E']-=2;
		}
		while (cnt['F']) {
			ans.emplace_back(5);
			cnt['F']--, cnt['I']--, cnt['V']--, cnt['E']--;
		}
		while (cnt['V']) {
			ans.emplace_back(7);
			cnt['S']--, cnt['E']-=2, cnt['V']--, cnt['N']--;
		}
		while (cnt['I']) {
			ans.emplace_back(9);
			cnt['N']-=2, cnt['I']--, cnt['E']--;
		}
		while (cnt['O']) {
			ans.emplace_back(1);
			cnt['O']--, cnt['N']--, cnt['E']--;
		}
		sort(ans.begin(), ans.end());
		cout << "Case #" << t << ": ";
		for (auto x : ans) cout << x;
		cout << '\n';
	}
}