[ 백준 BOJ ] 1148번 - 단어 만들기(C++)

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

 

생각 흐름

• map에 퍼즐판에 각 문자의 개수를 저장해준다.
• word들을 순회하면서 퍼즐 단어로 만들 수 있는지 확인한다.
  • 만들 수 있으면 각 word의 속한 문자에 대해 +1 해준다. 이때 map으로 저장해준다.
  • 만들 수 없으면 다음 단어로 넘어간다.

#include <iostream>
#include <vector>
#include <map>
#include <memory.h>

using namespace std;

vector<string> word;
map<char, int> m;
bool checked[30];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    while(true){
        string tmp;
        cin>>tmp;
        
        if(tmp=="-") break;
        
        word.push_back(tmp);
    }
    
    while(true){
        string tmp;
        cin>>tmp;
        
        if(tmp=="#") break;
        
        m.clear();
        
        map<char, int> ans;
        for(auto c : tmp){
            m[c]++;
            ans[c] = 0;
        }
        
        for(int i = 0; i<word.size(); i++){
            map<char, int> tmp = m;
            
            bool isNotOk = false;
            for(int j = 0; j<word[i].size(); j++){
                if(--tmp[word[i][j]]<0){
                    isNotOk = true;
                    break;
                }
            }
            if(!isNotOk){
                for(int j = 0; j<word[i].size(); j++){
                    if(checked[word[i][j]-'A']) continue;
                    checked[word[i][j]-'A'] = true;
                    ans[word[i][j]]++;
                }
                memset(checked, false, sizeof(checked));
            }
        }
        int smallNum=987654321, bigNum = -1;
        string small="", big="";
        for(auto a : ans){
            if(smallNum>=a.second){
                if(smallNum>a.second){
                    small=a.first;
                }else{
                    small+=a.first;
                }
                smallNum = a.second;
            }
            if(bigNum<=a.second){
                if(bigNum<a.second){
                    big=a.first;
                }else{
                    big+=a.first;
                }
                bigNum = a.second;
            }
        }
        
        cout<<small<<" "<<smallNum<<" "<<big<<" "<<bigNum<<endl;
    }
    
    return 0;
}