[BOJ/Gold 5] 백준 1501 영어 읽기(C++)

문제 링크

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

1501번: 영어 읽기

 

문제

혹시 인터넷을 하다가, 다음과 같은 식의 문장을 본 적이 있는가?

It is itnersetnig taht pepole can raed smoe grabeld wrods.

원래의 문장은 'It is interesting that people can read some garbled words'이다. 각각의 단어들은 제일 첫 문자와 제일 끝 문자를 제외하고는 순서가 뒤섞여 있다. 한 대학에서 시행한 연구 조사 결과에 따르면, (영어 단어를 아는 사람의 경우) 첫 문자와 제일 끝 문자가 일치하고, 그 사이의 문자들은 순서가 어떻게 뒤바뀌어 있더라도 읽는 데 지장이 없다고 한다.

그렇다보니, 한 단어가 여러 단어로 해석될 수도 있다. 예를 들어 abcde와 같은 단어는, abcde, abdce, acbde, acdbe, adbce, adcbe 같은 단어들로 해석될 수도 있다. 물론 각각의 단어들이 실제로 존재하는 단어(사전에 존재하는 단어)일 경우에만 의미가 있다.

영어 문장이 주어졌을 때, 그 문장을 해석하는 방법의 경우의 수를 구하는 프로그램을 작성하시오. 각각의 단어는, 첫 글자와 끝 글자가 일치하는 다른 단어(사전에 존재하는)로 해석할 수 있다. 영어 문장은 하나 이상의 단어로 이루어져 있으며, 각 단어들은 공백으로 구분되어 있다.

입력

첫째 줄에 사전에 있는 단어들의 개수 N(0 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄에 하나씩, 영어 사전에 있는 단어들이 주어진다. 각 단어의 길이는 100자를 넘지 않는다. 다음 줄에 해석할 문장의 개수 M(0 ≤ M ≤ 10,000)이 주어진다. 다음 M개의 줄에는 각 줄에 하나씩 문장이 주어진다. 각 문장의 길이는 10,000자를 넘지 않는다. 영어 단어는 알파벳 대소문자(구별됨)로만 이루어진다.

출력

M개의 줄에, 각 문장을 해석하는 경우의 수를 출력한다. 답은 32-bit signed int 범위 안에 있다고 가정하자.

예제 입력 1

3
ababa
aabba
abcaa
2
ababa
abbaa

예제 출력 1

2
2

알고리즘 분류

• 문자열
• 자료 구조

풀이

단어의 길이가 3 이상이라면, 맨 끝 양쪽의 알파벳만 일치한다면 가운데의 알파벳의 각각의 개수들만 일치한다면 해석이 가능한 걸로 간주한다. 따라서 N개의 단어 중 단어의 길이가 3 이상인 것들은 양 옆 알파벳을 제외한 가운데의 알파벳을 오름차순으로 정렬하고 map을 이용하여 정보를 정리해둔다.

그리고 M개의 문장을 입력받고, 공백 단위로 문장을 Tokenize해주는 Split 함수를 따로 구현하고 각각의 문장을 단어들로 Tokenize한다. 이 단어들을 역시 양 옆 알파벳을 제외한 가운데의 알파벳을 오름차순으로 정렬한다. map을 이용하여 기록해둔 정렬해둔 단어의 출몰(?) 횟수가 바로 단어의 해석 가능한 경우의 수가 된다.

어떤 문장의 모든 단어의 해석 가능한 경우의 수를 곱한 것이 바로 해당 문장의 해석 가능한 경우의 수가 된다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 10001
#define LL long long
#define INF 1e9

using namespace std;

int N, M;
string Dict;
unordered_set<string> SET;
unordered_map<string, int> MAP;
string S;
int answer;

vector<string> Split(string Str) {
	vector<string> res;
	string tmp = "";
	for (int i = 0; i < Str.size(); i++) {
		if (Str[i] == ' ') {
			res.push_back(tmp);
			tmp = "";
		}
		else {
			tmp += Str[i];
		}
	}
	res.push_back(tmp);
	return res;
}

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Dict;
		if (SET.find(Dict) == SET.end()) {
			SET.insert(Dict);
			string newDict = Dict;
			if (Dict.size() > 3) {
				sort(newDict.begin() + 1, newDict.end() - 1);
			}
			MAP[newDict]++;
		}
	}
	cin >> M;
}

void Find_Answer() {
	cin.ignore();
	while (M--) {
		answer = 1;
		getline(cin, S);
		vector<string> Vec = Split(S);
		for (int i = 0; i < Vec.size(); i++) {
			string Word = Vec[i];
			if (Word == "") {
				continue;
			}
			if (Word.size() > 3) {
				sort(Word.begin() + 1, Word.end() - 1);
			}
			answer *= MAP[Word];
		}
		cout << answer << "\n";
	};
}

int main() {
	FASTIO
	Input();
	Find_Answer();

	return 0;
}