백준 1501 : 영어 읽기(C++)

문제

풀이

이 문제는 문자열과 정렬을 이용해서 풀 수 있습니다.
예를 들어, ababa와 aabba라는 단어가 있으면 이 두 단어는 첫글자와 마지막 글자가 같고 사이에 있는 글자는 순서만 다릅니다. 따라서 해석할 때 여러 경우로 해석 될 수 있습니다. ababa, aabba, abbaa 3가지 경우로 해석 될 수 있습니다.

해결 방법은 첫글자와 마지막 글자를 제외하고, 사이에 있는 글자들을 정렬시켜 주는 것입니다. 그러면 위 3가지 경우 모두 aabba로 정렬되고 이를 통해 해석할 수 있는 경우를 찾을 수 있습니다.

그리고 문장에서의 경우에 수이기 때문에 각 단어의 경우의 수를 구해서 곱해주면 결과값을 얻을 수 있습니다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define endl "\n"
#define init ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int main() {
    init
    int N,T;
    vector<string> dictionary;

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

    cin >> T;
    cin.ignore();
    while(T--) {
        vector<string> stringInfo;
        string sentence;
        getline(cin, sentence);

        string word_ = "";
        for(int i = 0; i < sentence.length(); i++) {

            if(sentence[i] == ' ') {
                if(word_.length() > 3) {
                    sort(word_.begin()+1, word_.end()-1);
                }

                stringInfo.push_back(word_);
                word_ = "";
            }
            else if(i == sentence.length() - 1) {
                word_ += sentence[i];
                if(word_.length() > 3) {
                    sort(word_.begin()+1, word_.end()-1);
                }

                stringInfo.push_back(word_);
                word_ = "";
            }
            else {
                word_ += sentence[i];
            }
        }

        int mul = 1;
        for(int i = 0; i < stringInfo.size(); i++) {
            int count = 0;
            for(int j = 0; j < dictionary.size(); j++) {
                if(stringInfo[i] == dictionary[j]) {
                    count++;
                }
            }
            mul *= count;
        }
            cout << mul << endl;
    }
    return 0;
}