가르침

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 0934 ~ 1030
int N, K, ans;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K;
    map<char,bool> m;
    map<char,bool> need_flag;
    vector<string> sv;
    char need[5] = {'a', 'c', 'n', 'i', 't'};
    vector<char> v;
    for(int i=0;i<N;i++)
    {
        string s;
        cin >> s;
        sv.push_back(s);
        for(auto c : s)
        {
            if(c == 'a' or c == 'c' or c == 'n' or c == 'i' or c == 't')
                need_flag[c] = true;
            else m[c] = true;
        }
    }
    /* 최소 5개 단어는 있어야 함 */
    if(K < 5){
        cout << 0;
        return 0;
    }
    /* 최소 anta / tica를 구성하는 5개 단어는 있어야 함 */
    for(int i=0;i<5;i++)
        if(!need_flag[need[i]]){
            cout << 0;
            return 0;
        }
    for(auto it = m.begin();it != m.end();it++)
        v.push_back(it->first);

    int len = v.empty() ? 0 : v.size();
    int ch[len];
    fill(ch, ch+len, 1);
    /* 고를 수 있는 수가 나온 알파벳 종류보다 같거나 크다면 모든 단어를 말할 수 있다 */
    if(K-5 >= len){
        cout << sv.size();
        return 0;
    }
    for(int i=0;i<K-5;i++) ch[i] = 0;
    do{
        map<char,bool> tm;
        for(int i=0;i<len;i++)
            if(ch[i] == 0) tm[v[i]] = true;
        int cnt=0;
        for(int i=0;i<sv.size();i++)
        {
            string cur = sv[i];
            bool flag= true;
            for(auto a : cur)
                if(a == 'a' or a == 'c' or a == 'n' or a == 'i' or a == 't'){
                    continue;
                }else if(!tm[a]){
                    flag = false;
                    break;
                }
            if(flag == true) cnt++;
        }
        ans = max(ans, cnt);
    }while(next_permutation(ch, ch+len));
    cout << ans;
    return 0;
}

• 로직
  • 예외 처리
    • K가 5보다 작으면 종료 --> 필수 알파벳 5개 ('a' / 'c' / 'n' / 'i' / 't')는 있어야 하기 때문
    • 필수 알파벳 5개가 없으면 종료 --> 모든 단어에 들어가기 때문에 없으면 무조건 0
    • 필수 알파벳을 제외한 알파벳 수 <= K-5 이면 모든 알파벳을 알 수 있으니 단어의 총 개수가 정답
  • next_permutation()을 이용해서 가질 수 있는 알파벳 중 K-5개를 선택하는 조합으로 수행
  • 최대 카운트 세기

• 주의할 점
  • 시간복잡도 미리 계산해보기
    • 필수 알파벳를 제외하지 않고 총 26개중 알파벳 중에서 고르는 최대값인 26C13 = 약 1천만 경우의수
    • 최대 50개의 단어와 최대 15길이를 가짐
    • 총 1천만 * 50 * 15 = 약 7.5억 --> 시간초과
    • 해법
      : 필수 단어인 5개를 제외하면 21C10 -> 약 35000개의 연산으로 줄어듬
      총 21C10 * 50 * 15 = 약 2600만 --> 시간 충분
  • 예외 처리
    : K-5가 현재 알파벳 개수보다 더 많으면 ch초기화시 범위를 벗어난다 --> 조심