[c++] BOJ 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 같은 단어들로 해석될 수도 있다. 물론 각각의 단어들이 실제로 존재하는 단어(사전에 존재하는 단어)일 경우에만 의미가 있다.

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

 

풀이

단어의 중간 부분이 변경되는 경우도 같은 단어라고 취급하므로 단어의 중간 부분을 정렬한 것은 단어 집합의 key가 된다. 똑같은 단어가 들어올 수도 있으므로 unordered_set으로 같은 key를 가지는 단어들은 저장해둔 후, 문장에서 단어를 하나씩 체크하면서 같은 key에 해당하는 단어의 개수를 곱해주면 문장을 해석할 수 있는 경우의 수가 나오게 된다.

 

코드

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <sstream>

using namespace std;

unordered_map<string, unordered_set<string>> wordSet; // number였다가 겹치는 단어가 있을 까봐 바꿈

int main() {
	int N;
	cin >> N;

	while (N--) {
		string word; cin >> word;
		string original = word;
		if(word.length() > 3){
			sort(word.begin() + 1, word.end() - 1);
		}

		if (wordSet.find(word) == wordSet.end()) {
			wordSet[word] = unordered_set<string>();
		}
		wordSet[word].insert(original);
	}

	int M; cin >> M;
	cin.ignore(); // '\n' 제거하기

	while (M--) {
		string word;
		long long result = 1;
		
		getline(cin, word);
		
		size_t iter = word.find(' ');
		
		vector<string> check;
		stringstream ss(word);
		string temp;
		
		while (getline(ss, temp, ' '))
		{
			check.push_back(temp);
		}
		
		for(int i=0; i<check.size(); i++){
			string target = check[i];
			
			if(target.length() > 3){
				sort(target.begin()+1, target.end()-1);
			}
			
			result *= wordSet[target].size();
		}
		
		cout << result << '\n';
	}
}

 

• c++에서 한 줄을 통째로 받고 space를 구분자로 하여 단어를 추출하는 과정이 쉽지 않다. 먼저, cin 입력은 공백이나 '\n' 문자를 버퍼에 저장해두고 무시한 채 변수에 입력값을 넣기 때문에 cin 입력을 받고 나면 버퍼에 공백이나 '\n' 문자가 남아있게 된다. getline 함수로 한 줄의 입력을 받을 수 있지만 해당 함수는 '\n'이 입력되면 종료되기 때문에 먼저 실행된 cin으로 인해 버퍼에 남아있던 '\n'문자가 들어갈 수 있다.
• 따라서 cin 후 getline을 실행할 때는 cin.ignore() 함수를 통해 버퍼를 비운 후 실행해주어야 한다. 또한, 해당 문제에서 geline을 통해 한 줄을 한꺼번에 받게 되면 버퍼의 크기가 부족해서 런타임에러가 발생하기 때문에 공백문자(' ')를 이용하여 단어마다 끊어서 받는 식으로 코드를 작성해야 한다.
• 단어의 길이가 2 이하인 경우는 굳이 정렬할 필요없이 자기 자신을 key로 사용하면 된다.

 

결과