백준 1062

문제를 처음 보고 했던 생각은 bool 배열을 이용해 사용된 알파벳을 체크하는 식으로 풀어볼까?였다.

거기에 더해, N의 최대값이 50, K의 최대값이 26이니 Brute Force로 풀 수 있으니 쉽겠네!! 라는 안일한 마음으로 덤볐다.

하지만 시간초과에 처참하게 녹았고...(이 글을 보는 사람들도 대다수 문제 풀이는 알겠지만, 시간 초과에 막혀서 여기로 왔을 거라 생각한다.)

 

이제 서론은 끝내고 풀이 방식에 대해 소개하도록 하겠다.

내 풀이 흐름은

1. anta와 tica를 제거한다.

2. 제거한 후 입력받은 문자열에 대해 각 문자의 값을 bit mask를 이용해 기록한다.(왜 비트마스크를 사용했는 지는 뒷부분에 있다.)

3. 문제에 주어진 모든 단어에 속한 알파벳들을 bit mask를 이용해 벡터에 저장한다.(위 3과 비교를 편하게 하기 위함)

4. 벡터를 순회하면서 "선택한 알파벳"을 bit mask의 형태로 갖고 있는 값에 추가한다.

5. "선택한 알파벳"의 수가 벡터의 수와 같아지거나(더 이상 선택할 알파벳이 없거나), "선택한 알파벳"의 수가 "선택해야할 알파벳"의 수(K)값과 같아질 때, 3번에서 저장한 bit mask 와 "선택한 알파벳"의 bit mask를 차집합을 이용해 체크한다.(단어에 포함된 알파벳이 모두 "선택한 알파벳"에 포함되는가 판별)

6. 5의 상황이 모두 완료되면 반환(return)한다.

이렇게 된다.

코드를 보면

//2021.09.30
#include<iostream>
#include<vector>
#include<string>
using namespace std;

int n, k;
int alpNum = 5;
int alp = 0;
int word[50];
int check = 0;
int ans = 0;
int vlen;
vector<int> v;
void go(int idx){
    if(k==alpNum || vlen==alpNum-5){
        int cnt = 0;
        for(int i = 0; i < n; i++){
            if(word[i]&(~check)) continue;
            else cnt++;
        }
        if(cnt > ans) ans = cnt;
        return;
    }
    for(int i = idx; i < vlen; i++){
            check += v[i];
            alpNum++;
            go(i+1);
            check -= v[i];
            alpNum--;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> k;
    if(k < 5){
        cout << 0;
        return 0;
    }
    else if(k == 26){
        cout << n << '\n';
        return 0;
    }

    check += ((1<<('a'-'a')) + (1<<('n'-'a')) + (1<<('t'-'a')) + (1<<('i'-'a')) + (1<<('c'-'a')));
    for(int i = 0; i < n; i++){
        string temp;
        cin >> temp;
        temp = temp.substr(4, temp.length());
        for(int i = 0; i < 4; i++){
            temp.pop_back();
        }
        for(char c: temp){
            int x = (1<<(c-'a'));
            if(!(word[i]&x)) word[i] += x;
            if(!(alp&x) && !(check&x)) {
                v.emplace_back(x);
                alp += x;
            }
        }
    }
    vlen = v.size();
    go(0);
    cout << ans;
    return 0;
}

이렇게 되는데,

alpNum은 선택된 알파벳의 수, alp는 선택 가능한 알파벳을 bit mask로 저장, word는 각 단어를 bit mask로 저장, check는 선택된 알파벳을 bit mask로 저장, v는 선택 가능한 각 알파벳의 bit mask 값(alp변수와 같이 씀으로 반복문의 횟수를 줄이기 위해 추가했다), vlen은 v의 길이이다.

 

여기서 눈 여겨보아야 할 부분을 소개하겠다.

위 코드는 2와 3에 해당하는 부분인데, bitmask 형태로 각 단어에 포함된 알파벳값을 word[i]에, 모든 단어에 포함된 알파벳을 v와 alp에 각각 추가하는 과정이다.

그리고 이를 통해,

위 코드를 실행할 수 있는데, 위 코드는 if는 5의 과정 for는 4의 과정을 따른다고 보면 된다.

여기서 go 함수의 매개인자로 idx를 넘겨주는 것은, 이전 값에 대한 비교를 피하기 위함으로 k=2이고 vlen=5일 때, {v[0], v[1]}을 보는 것과 {v[1], v[0]}을 보는 것은 중복된 경우를 검사하는 것으로 배제하기 위해, idx값에 직전 비교가 어디서 끝났는 지(i+1, 정확히는 다음 go 함수가 어느 인덱스부터 비교를 시작해야하는 지)를 넣음으로 n^2을 n!로 시간복잡도를 줄이는 역할을 한다.

 

이걸로 풀이는 끝이며 혹시 질문이 있다면 댓글로 달아주기를 바란다.

 

p.s. 코딩테스트는 최근에 시작하여 푼 문제도 꽤나 쌓였지만, 지금까지는 내 풀이가 그렇게 최적화 되어 있지도, 남들보다 그렇게 나은 점도 없어 보여 포스팅을 삼가했다.

하지만, 이제부터는 풀었던 문제 중 어려웠거나, 고민을 많이 하거나, 검색 결과에 풀이가 별로 없는 또는 풀이가 자신 있는 경우에 대해 이렇게 포스팅으로 남기려 한다.

부족한 글에 부족한 풀이일 수도 있지만, 도움이 되었으면 좋겠다.