문제 정의
퍼즐(puzzle) 문자열이 하나 주어져 있을 때, 어떤 단어(word)가 유효(valid)하려면 다음 두 조건을 모두 만족해야 합니다.
- 단어에는 반드시 퍼즐의 첫 번째 글자가 포함되어야 합니다.
- 단어를 구성하는 모든 글자가 퍼즐 안에 존재해야 합니다.
예를 들어 퍼즐이 "abcdefg"라고 가정해 보겠습니다. 이때 "face", "cabbage" 같은 단어는 유효합니다. 반면 "beefed"는 'a'가 없어서, "based"는 퍼즐에 없는 's'가 포함되어 있어서 유효하지 않습니다.
우리가 구해야 하는 것은 답 목록입니다. 여기서 answer[i]는 i번째 퍼즐 puzzles[i]에 대해 주어진 단어 목록 words 중에서 유효한 단어의 개수를 의미합니다.
입력 및 출력 예시
입력이 다음과 같다고 가정해 보겠습니다.
words = ["aaaa","asas","able","ability","actt","actor","access"]
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
이때 출력은 [1,1,3,2,4,0]이 됩니다. 그 이유는 다음과 같습니다.
- "aboveyz"에 대한 유효한 단어: "aaaa" → 1개
- "abrodyz"에 대한 유효한 단어: "aaaa" → 1개
- "abslute"에 대한 유효한 단어: "aaaa", "asas", "able" → 3개
- "absoryz"에 대한 유효한 단어: "aaaa", "asas" → 2개
- "actresz"에 대한 유효한 단어: "aaaa", "asas", "actt", "access" → 4개
- "gaswxyz"에 대한 유효한 단어: 없음 → 0개 (목록의 어떤 단어도 'g'를 포함하지 않기 때문)
접근 방법: 비트마스크 활용
이 문제는 비트마스크(bitmask) 기법으로 효율적으로 해결할 수 있습니다. 알파벳은 총 26개이므로, 단어나 퍼즐에 등장하는 글자들의 집합을 26비트 정수 하나로 표현할 수 있습니다.
1. getMask() 함수 정의
문자열 s를 받아, s에 포함된 각 글자에 해당하는 비트를 설정한 마스크 값을 반환하는 함수입니다.
- mask := 0으로 초기화합니다.
- i := 0부터 s의 길이까지 반복하며 mask := mask OR 2^(s[i] - 'a') 연산을 수행합니다.
- 최종 mask를 반환합니다.
2. 메인 로직
- 결과를 저장할 배열 ans와 맵 m을 선언합니다.
- 모든 단어 w[i]에 대해 마스크를 계산한 뒤 m[mask]의 개수를 1씩 증가시켜, 같은 글자 집합을 가진 단어들을 그룹화합니다.
- 각 퍼즐 p[i]에 대해서는 다음을 수행합니다.
- word := p[i], mask := getMask(word)
- first := 2^(word[0] - 'a') — 퍼즐 첫 글자에 해당하는 비트
- current := mask로 초기화한 후, current > 0인 동안 반복합니다.
- current & first가 0이 아니면(첫 글자 비트를 포함하는 부분집합이면) temp += m[current]
- current := (current - 1) AND mask — mask의 모든 부분집합을 순회하는 표준 기법
- temp를 ans 끝에 추가하고, 모든 퍼즐에 대해 반복한 뒤 ans를 반환합니다.
핵심 아이디어는 current = (current - 1) & mask 연산을 통해 mask의 모든 부분집합을 빠짐없이 순회할 수 있다는 점입니다. 각 부분집합이 퍼즐의 첫 글자 비트를 포함하는지 검사하고, 포함한다면 해당 마스크를 가진 단어의 개수를 누적합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
typedef long long int lli;
class Solution {
public:
lli getMask(string s){
lli mask = 0;
for(int i =0;i<s.size();i++){
mask|= 1<<(s[i]-'a');
}
return mask;
}
vector<int> findNumOfValidWords(vector<string>& w, vector<string>& p) {
vector <int> ans;
map <lli, lli > m;
for(int i =0;i<w.size();i++){
string word = w[i];
lli mask = 0;
for(int j =0;j<word.size();j++){
mask|= getMask(w[i]);
}
m[mask]++;
}
for(int i = 0; i<p.size();i++){
string word = p[i];
lli mask = getMask(word);
lli first = 1<<(word[0]-'a');
lli current = mask;
lli temp = 0;
while(current>0){
if(current & first)temp+=m[current];
current = (current-1)&mask;
}
ans.push_back(temp);
}
return ans;
}
};
main(){
Solution ob;
vector<string> v = {"aaaa","asas","able","ability","actt","actor","access"};
vector<string> v1 = {"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};
print_vector(ob.findNumOfValidWords(v,v1));
}
입력
{"aaaa","asas","able","ability","actt","actor","access"},
{"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"}출력
[1, 1, 3, 2, 4, 0]
정리
이 풀이에서는 단어마다 한 번씩 마스크를 계산해 맵에 개수를 저장하고, 각 퍼즐에 대해서는 해당 퍼즐 마스크의 부분집합만 순회하므로 모든 단어-퍼즐 조합을 일일이 비교하는 브루트포스 방식보다 훨씬 효율적입니다. 특히 퍼즐 길이가 최대 7글자로 제한되는 경우 부분집합의 수는 최대 128개이므로, 비트마스크와 부분집합 열거 기법을 활용하면 대량의 입력에서도 빠르게 답을 구할 수 있습니다.