BOGGLE.cpp

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>

using namespace std;

// 단어의 사이즈를 점수로 변환
const int size2score[9] = {-987654321, 0, 0, 1, 1, 2, 3, 5, 11};

// set 정렬을 위해서 string 길이 대소 판별 정의
struct string_greater
{
    bool operator()(string a, string b)
    {
	if(a.size() == b.size()) // 길이가 같을 땐 사전식 정렬
	{
	    for(int i = 0; i < a.size(); ++i)
	    {
		if(a[i] != b[i])
		    return a[i] < b[i];
	    }
	}
	else // 길이가 다르면 큰 것이 우선
	    return a.size() > b.size();
    }
};

// function_name : find_dic2boggle
// Object : 1) small_map의 key가 모두 large_map에 포함되느냐
//          2) 1)이 만족한다면 small_map의 각 key의 value보다 large_map의 각 key의 값이 크냐
//          3-1) 2)가 만족한다면 true
//          3-2) 1), 2) 중 어느 것도 만족시키지 못한다면 false
bool find_dic2boggle(map<char, int> large_map, map<char, int> small_map)
{
    map<char, int>::iterator iter;
    for(map<char, int>::iterator small_iter = small_map.begin(); small_iter != small_map.end(); ++small_iter)
    {
	iter = large_map.find(small_iter->first);
        if(iter != large_map.end())
        {
     	    if(small_iter->second > iter->second)
	        return false;
        }
        else
	    return false;
    }
    return true;
}

// function_name : get_score
// Object : 1) found_string의 각 원소의 길이를 받아 size2score에 의해 총 점수를 반환
int get_score(set<string, string_greater> found_string)
{
    int score = 0;
    for(set<string>::iterator set_iter = found_string.begin(); set_iter != found_string.end(); ++set_iter)
	score += size2score[set_iter->size()];
    return score;
}

int main()
{
//////////////////////////// 입력부 시작 /////////////////////////////
    int num;
    cin >> num; // 사전 단어 개수 받음
    pair< map <char, int>::iterator, bool > pr;
    map< string, map < char, int > > dic_map;
    string input_string;
    getline(cin, input_string); // blank 처리
    for(int i = 0; i < num; i++)
    {
	map<char, int> each_string_map;
        getline(cin, input_string);
        for(int j = 0; j< input_string.size(); j++)
	{
	    pr = each_string_map.insert(pair<char, int>(input_string[j], 1)); // char 삽입 시도
	    if(false == pr.second) // 이미 있다면 value 1 증가
		(pr.first->second)++;
	}
	dic_map.insert(pair<string, map<char, int> >(input_string, each_string_map));
    }
    // 1-1. 사전에 해당하는 dic_vector 입력 완료

    cin >> num; // BOGGLE의 개수 받음
    vector< map <char, int> > boggle_vector; // 각 boggle map을 저장하는 백터
    getline(cin, input_string); // blank 처리
    for(int i = 0; i < num; i++)
    {
	map<char, int> each_boggle_map;
        for(int j = 0; j < 4; j++)
        {
            getline(cin, input_string);
            for(int k = 0; k < 4; k++)
	    {
		pr = each_boggle_map.insert(pair<char, int>(input_string[k], 1));   
		if(false == pr.second)
			(pr.first->second)++;
	    }
        }
        boggle_vector.push_back(each_boggle_map);
	getline(cin, input_string); // blank 처리
    }
    // 1-2. boggle에 해당하는 boggle_vector 입력 완료
/*
    // 입력 확인 test 시작
    for(map<string, map<char, int> >::iterator i = dic_map.begin(); i != dic_map.end(); ++i)
    {
	cout << i->first << ':';
	for(map<char, int>::iterator j = (i->second).begin(); j != (i->second).end(); ++j)
	    cout << '(' << j->first << ',' << j->second << ')';
	cout << endl;
    }

    for(vector<map<char, int> >::iterator i = boggle_vector.begin(); i != boggle_vector.end(); ++i)
    {
	for(map<char, int>::iterator j = i->begin(); j != i->end(); ++j)
	    cout << '(' << j-> first << ',' << j->second << ')';
	cout << endl;
    }
*/
/////////////////////////////// 입력부 종료 /////////////////////////////

    // *boogle_iter는 각 boogle의 map<char, int>이다
    // dic_iter->first는 dic에 해당하는 각 string, dic_iter->second는 그 string의 map<char, int>이다
    for(vector<map<char, int> >::iterator boggle_iter = boggle_vector.begin(); boggle_iter != boggle_vector.end(); ++boggle_iter)
    {
	set<string, string_greater> found_dic; // 각 boggle안에서 찾아낸 string의 set
	for(map<string, map<char, int> >::iterator dic_iter = dic_map.begin(); dic_iter != dic_map.end(); ++dic_iter)
	{
	    if(find_dic2boggle(*boggle_iter, dic_iter->second) == true)
		found_dic.insert(dic_iter->first);
	}
        // 각 boggle에 대한 결과 출력 시작
        cout << get_score(found_dic) << ' ' << *(found_dic.begin()) << ' ' << found_dic.size() << endl;
    }
    return 0;
}