(출처) https://www.acmicpc.net/problem/1062
완전탐색으로 풀 수 있을 것 같긴 한데
문제를 읽어보니 26개의 알파벳 중 학생에게 가르칠 알파벳 k 개를 고르는 조합 문제인 것 같았다.
따라서 총 26개의 알파벳으로 표현할 수 있는 모든 조합 경우를 만들고, 만든 경우를 입력으로 주어진 단어들과 전부 비교해 보면서 최댓값을 리턴하는 경우를 찾아주면 될 것 같았다.
이때 26개의 원소로 만들 수 있는 조합 경우의 수는 2^26 = 약 6000만 개인데, 6000만 개의 경우를 만들고 끝인 게 아니라 추가적으로 각 경우들을 입력으로 들어오는 50개의 단어와 비교를 해야 하므로, 6천만 * 50 = 약 30억 번 정도의 연산이 필요하게 된다.
30억의 연산은 문제에서 주어진 1초라는 시간제한으로는 절대로 해결할 수 없지만, 그냥 무작정 계산을 때려 박아도 30억 정도인데 이 정도 규모라면 최적화를 작업을 거치면 그래도 해볼 만하지 않을까라고 생각했다.
최적화를 시킬 만한 요소(시간복잡도)
먼저 문제에서 남극의 단어는 모두 a, c, i, t, n 이라는 알파벳이 포함되어 있다는 조건을 주었다.
이 조건을 이용하면 위 5개의 알파벳은 조합을 만드는 과정에서 배제시켜도 되므로 총 21개의 원소만으로 조합을 만들면 된다. 따라서 존재하는 조합의 경우의 수는 2^21 = 약 2000만 개로 줄어든다.
조합의 경우의 수가 아무리 2000만 개로 줄었다고 하더라도, 2000만 개의 모든 경우를 50개의 단어와 전부 비교를 해버리게 되면 1억이 넘는 연산 회수를 거쳐야 한다.
그런데 생각을 해보면 당연하게도 굳이 2000만 개를 전부 50개의 단어와 비교를 할 필요가 없다.
어차피 문제에서 학생에게 가르칠 수 있는 단어의 개수 k를 정해주므로, 21개의 원소 중에 k 개를 뽑은(정확히는 앞에서 사용한 5개의 알파벳을 제외한 k-5개) 경우의 수만 추려내어 50개의 단어와 비교하면 된다.
만약 k가 10으로 주어졌을 경우 21 C 10 == 대략 30만인데 30만 개의 경우를 50개의 단어와 비교한다고 하면 50 * 30만 = 1500만 번의 연산이 필요하다.
따라서 2000만 + 1500만 = 3500만 정도의 연산 회수라면 충분히 1초라는 시간제한 안에 해결할 수 있어 보였다.
비트마스킹을 이용한 구현
위 로직을 비트마스킹을 이용하기로 구현하기로 했다.
1 << 21 번의 for문을 돌려서 만들 수 있는 조합 경우를 모두 만들고, 각 경우마다 켜져 있는 1의 비트 수를 센다.
이때 켜져 있는 비트의 수가 k 개를 만족하지 못하는 경우 그냥 continue 시키고, 만족시키는 경우에만 입력으로 주어진 단어들과 비교하는 추가 작업을 진행한다.
이때 주어진 단어들도 비트 형식으로 변환하여 비교를 진행하는데, 조합의 비트와 주어진 단어의 비트를 비교하여 조합의 비트가 단어의 비트를 모두 포함시키는 경우라면 ret을 +1 해주고 아니라면 그냥 넘어간다.
포함의 유무를 판단하는 과정은 조합의 비트와 단어 비트를 or 연산시켜 연산된 값에 변화가 있는지를 체크하였다.
연산된 값이 변화하였다는 것은 조합비트에 포함되어 있지 않은 비트가 단어 비트에 존재한다는 뜻으로 즉 현재 뽑은 알파벳 이외의 다른 알파벳이 단어에 포함되어 있다는 뜻이다.
최종적으로는 모든 조합 중 가장 큰 ret을 갖은 녀석을 return 해주면 된다.
시간초과 코드
#pragma warning (disable : 4996)
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
char alphabet[21] = {'b','d','e','f','g','h','j','k','l','m','o','p','q','r','s','u','v','w','x','y','z' };
map<char, bool> m;
vector<string> words;
bool checking_bit(int i,int num) {
int mask = 1 << i;
if ((num & mask)) return true;
else return false;
}
int solution(int k) {
int ret = 0;
for (int i = 0; i < (1 << 21); i++) {
int temp_ret = 0;
int temp_k = k;
for (int j = 0; j < 21; j++) {
bool check = checking_bit(j, i);
if (check) temp_k--;
}
if (temp_k == 0) {
map<char,bool> temp_m = m;
for (int j = 0; j < 21; j++) {
bool check = checking_bit(j, i);
if (check) {
temp_m[alphabet[j]] = true;
}
}
for (string word : words) {
bool is_ok = true;
for (int j = 0; j < word.size(); j++) {
if (temp_m.find(word[j]) != temp_m.end()) continue;
else {
is_ok = false;
break;
}
}
if (is_ok) temp_ret++;
}
}
ret = max(ret, temp_ret);
}
return ret;
}
int main(){
int n, k;
cin >> n >> k;
words = vector<string>(n);
m['a'] = true, m['c'] = true, m['i'] = true, m['n'] = true, m['t'] = true;
for (int i = 0; i < n; i++) {
string temp;
cin >> temp;
words[i] = temp;
}
if (k < 5) {
cout << "0\n";
return 0;
}
int ret = solution(k - 5);
cout << ret << "\n";
return 0;
}완벽히 최적화 과정을 거치지 않았더니 시간초과가 났던 코드.
조합 경우의 수만 비트마스킹 처리하였기 때문에 조합이, 주어진 단어들과 매칭되는지 판단하기 위해서 불필요한 여러 가지 과정들이 들어가 버리게 되었다.
(조합에 켜져 있는 비트에 해당하는 알파벳 철자를 따로 map에 모아놓고, 이후 단어의 글자들을 전부 탐색하면서 map에 존재하는지를 판단하는 등)
따라서 해당 과정에서 기존의 계산했던 시간복잡도보다 더 많은 연산을 진행하게 되었다.
따라서 조합뿐만 아니라 주어진 단어들도 전부 비트마스킹 처리하여 계산을 진행하였다.
비트마스킹 코드
#pragma warning (disable : 4996)
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
vector<string> words;
vector<int> bit_words;
char alphabet[21] = { 'b','d','e','f','g','h','j','k','l','m','o','p','q','r','s','u','v','w','x','y','z' };
int making_bitmask(string word) {
int num = 0;
string middle = word.substr(4);
middle = middle.substr(0, middle.size() - 4);
for (char ch : middle) {
int index = -1;
for (int i = 0; i < 21; i++) {
if (ch == alphabet[i]) {
index = i;
break;
}
}
if (index == -1) continue;
int mask = 1 << index;
num = num | mask;
}
return num;
}
int checking_bit(int num) {
int ret = 0;
for (int i = 0; i < 21; i++) {
int mask = 1 << i;
if ((num & mask)) ret++;
}
return ret;
}
int solution(int k) {
int ret = 0;
for (int i = 0; i < (1 << 21); i++) {
int temp_ret = 0;
if (checking_bit(i) == k) {
for (int bit : bit_words) {
int bitmask = bit | i;
if (i == bitmask) temp_ret++;
}
}
ret = max(ret, temp_ret);
}
return ret;
}
int main(){
int n, k;
cin >> n >> k;
words = vector<string>(n);
for (int i = 0; i < n; i++) {
string temp;
cin >> temp;
words[i] = temp;
}
if (k < 5) {
cout << "0\n";
return 0;
}
bit_words.clear();
for (string word : words) {
int bit = making_bitmask(word);
bit_words.push_back(bit);
}
int ret = solution(k - 5);
cout << ret << "\n";
return 0;
}