[백준/C++]1062번_가르침

문제는 다음과 같습니다.

먼저 이 문제를 두 번 풀었는데,
첫 번째 풀이는 비트마스크 없이 일일이 문자열을 비교해서 계산한 풀이와
두 번째 풀이는 비트마스크를 이용하여 문자열 비교시에 시간복잡도를 개선한 풀이입니다.

일단, 저는 재귀를 이용하지 않고
next_permutation을 이용한 조합으로 경우의 수를 계산하였습니다.

또한 26개 - (5개: a, c, i, n, t) = 21개
21개에서 조합을 뽑지 않고
입력받은 모든 문자열에서 포함한 문자내에서만 조합을 돌리도록 계산하였습니다.

⭐️ string s -> 한 번씩 등장한 알파벳을 모아놓은 문자열

조합을 돌면서,
각 단어를 이루는 문자가 해당 조합 내의 단어에 모두 포함되어 있으면 개수를 count 해주는 식으로 계산하였습니다.

💡 풀이 1

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
using namespace std;

int N, K;
int a[26] = {0, };
int res = 0;
vector<string> v;
vector<int> ind;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N >> K;
    if(K<5){
        cout << 0 << endl;
        exit(0);
    }
    string s;
    for(int i=0; i<N; i++){
        cin >> s;
        s = s.substr(4, s.size()-8);
        sort(s.begin(), s.end()); // 정렬
        s.erase(unique(s.begin(), s.end()), s.end()); // 중복 제거
        for(int j=0; j<s.size(); j++){
            a[s[j]-'a']++;
        }
        v.push_back(s);
    }

    a[0] = 0; a[2] = 0; a[8] = 0; a[13] = 0; a[19] = 0;
    s = "";

    for(int i=0; i<26; i++){
        if(a[i]) s += i + 'a';
    } // s -> 한 번씩 등장한 알파벳들 모임

    // cout << s << endl;

    if(K-5 >= s.size()){ // 예외처리 -> 조합 뽑을 때 nCk 에서 k가 더 큰 경우
        cout << N << endl;
        exit(0);
    }

    for(int i=0; i<K-5; i++) ind.push_back(1);
    for(int i=0; i<s.size()-(K-5); i++) ind.push_back(0);
    sort(ind.begin(), ind.end());


    do{
        // 한 조합에 대해서
        int b[26] = {0, };
        b[0] = 1; b[2] = 1; b[8] = 1; b[13] = 1; b[19] = 1;

        for(int i=0; i<ind.size(); i++){
            if(ind[i]) b[s[i]-'a']=1;
        }

        int cnt = 0;
        for(int i=0; i<v.size(); i++){ // 단어 개수
            int state = 0;
            for(int j=0; j<v[i].size(); j++){ // 각 단어에 대해서
                if(b[v[i][j]-'a']==0){
                    state = 1;
                    break;
                }
            }
            if(state==0) cnt++;
        }

        res = max(res, cnt);
        
    }while(next_permutation(ind.begin(), ind.end()));

    cout << res << endl;
    return 0;
}

---

💡 풀이 2 -> 각각의 문자에서 문자열 비교시에 비트마스크 이용

개선된 방법은 다음과 같습니다.

입력받은 단어를 문자열로 저장하는 것이 아닌,
각 단어에서 단어를 구성하고 있는 알파벳을 비트마스크로 저장하였습니다.

for(int j=0; j<s.size(); j++){ // 한 단어에 대해서
    v[i] |= (1 << (s[j]-'a')); // 단어를 이루는 알파벳의 비트마스크를 저장
    a[s[j]-'a']++;
}

그래서, 해당 조합으로 만들어진 문자열 -> 비트로 바뀐 수(n)
n과 각각의 단어를 비교하면 됩니다.
O(N*(각 단어의 길이))에 해당하는 시간복잡도를 ➡️ O(N*1) 만큼 개선할 수 있습니다.
비교하는 코드는 다음과 같습니다.

for(i=0; i<N; i++){ // 각 단어에 대해서
    if((v[i] & ((1<<26)-1-n)) == 0) cnt++; // 배우지 않는다고 한 알파벳이 단어에 없으면 -> 배울 수 있음
}

전체 코드는 다음과 같습니다🙆🏻‍♀️

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
using namespace std;

int N, K;
int a[26] = {0, };
int res = 0;
int v[51] = {0, };
vector<int> ind;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N >> K;
    if(K<5){
        cout << 0 << endl;
        exit(0);
    }
    string s;
    for(int i=0; i<N; i++){
        cin >> s;
        for(int j=0; j<s.size(); j++){
            v[i] |= (1 << (s[j]-'a'));
            a[s[j]-'a']++;
        }
    }

    a[0] = 0; a[2] = 0; a[8] = 0; a[13] = 0; a[19] = 0;
    s = "";

    for(int i=0; i<26; i++){
        if(a[i]) s += i + 'a';
    } // s -> 한 번씩 등장한 알파벳들 모임


    if(K-5 >= s.size()){ // 예외처리 -> 조합 뽑을 때 nCk 에서 k가 더 큰 경우
        cout << N << endl;
        exit(0);
    }

    for(int i=0; i<K-5; i++) ind.push_back(1);
    for(int i=0; i<s.size()-(K-5); i++) ind.push_back(0);
    sort(ind.begin(), ind.end());


    do{
        // 한 조합에 대해서
        int n = 532741;

        for(int i=0; i<ind.size(); i++){
            if(ind[i]) n |= ( 1 << ((s[i]-'a')) );
        }

        int cnt = 0;
        int i;
        for(i=0; i<N; i++){ // 각 단어에 대해서
            if((v[i] & ((1<<26)-1-n)) == 0) cnt++;
        }
        res = max(res, cnt);
        
    }while(next_permutation(ind.begin(), ind.end()));

    cout << res << endl;
    return 0;
}

---

1 -> 2로 풀이를 개선하였을 때에 개선된 시간을 확인할 수 있었습니다.