취미로 코딩하기

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

이번에 볼 문제는 백준 29779번 문제인 Colliding Encoding이다.
문제는 아래 링크를 확인하자.

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

주어지는 문자열들의 각 문자를 주어진 규칙대로 치환해 얻을 수 있는 변환된 문자열들 사이에 겹치는 것이 있는지 확인하는 문제이다. 주어진 작업을 그대로 구현해 문제를 해결하자.

한편, 문자열의 길이가 최대 9로 충분히 짧아 변환된 문자열을 정수로 기록하는 것으로 메모리를 절약해 실행 속도 향상을 노릴 수 있다. 다만, 이와 같은 풀이를 이용하고자 할 경우 0으로 시작하는 문자열과 leading zero가 있는 문자열은 구분이 되어야 하므로, 자릿수 없음을 나타내는 수를 별도로 하나 더 할당하는 방법, 자릿수를 같이 저장하는 방법 등의 예외처리가 추가로 필요하다.

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

#include <iostream>
#include <string>
#include <set>
using namespace std;
typedef long long ll;

int N;
set<ll> st;
int A[128];

void solve() {
	st.clear();
	for (char c = 'A'; c <= 'Z'; c++) cin >> A[c];
	cin >> N;
	for (int i = 0; i < N; i++) {
		string s; cin >> s;
		while (s.length() < 9) s += '#';
		ll val = 0;
		for (auto &l : s) val = val * 10 + A[l];
		st.insert(val);
	}
	if (st.size() < N) cout << "YES\n";
	else cout << "NO\n";
}

int T;

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

	A['#'] = 10;

	cin >> T;
	for (int t = 1; t <= T; t++) {
		cout << "Case #" << t << ": ";
		solve();
	}
}