[LeetCode] 1178. Number of Valid Words for Each Puzzle

https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/

Number of Valid Words for Each Puzzle - LeetCode

Number of Valid Words for Each Puzzle - Hard

 

 

words와 puzzles가 주어진다.

puzzles의 각각의 puzzle 당 해당 조건을 만족하는 words내의 word 개수를 저장하여 출력하는 문제다.

조건은 다음과 같다.

 

1. word가 puzzle의 첫 알파벳으로 시작해야한다.

2. word내의 알파벳은 모두 puzzle에 포함되어야 한다.

 

간단해보이지만 절대 간단하지만은 않은 문제다.

hash map을 쓰면 간단히 해결되지 않을까 생각했다.

puzzle의 알파벳을 모두 map으로 저장하고 각각의 word를 훑으며 map에 있을경우 count++을... 생각하다가

이 경우 puzzles의 puzzle을 모두 순환하고(10^4) 그때마다 puzzle의 알파벳(7) 및, words와(10^5) word의 알파벳(50)을 모두 순환해야한다.

최악의 경우에 대충 계산해봐도 10^4 * (7 + 10^5*50) => 약 10^10 이상의 연산이 필요하다.

힌트를 보니 bitmask를 사용하라고 나와있었다.

아! word의 bitmask를 먼저 벡터나 map으로 저장해놓고,

puzzle의 bitmask와 & 했을때 word의 bitmask가 나오면 되겠다 생각했다.

하지만 안된다.

 

이 경우엔 word 를 한번씩 (10^5 * 50), puzzle 당 word를 한번씩 (10^4 * 10^5) 이므로 10^10 이상보단 작지만 10^9 정도의 연산이 필요하다.

 

여러 고민을 해보다가 결국 Solution을 참고했다.

https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/solution/

Number of Valid Words for Each Puzzle - LeetCode

 

풀이는 아래와 같다.

word를 먼저 bitmask로 모두 변환한 후 map에 매핑한다. (같은 것이 있을 경우 ++)

puzzle도 bitmask로 변환하는데, puzzle의 맨 앞알파벳을 따로 변환하고, => 이를 first라 하자.

두번째 알파벳부터를 따로 변환한다. => 이를 mask라 하자.

 

맨 처음 map에서 first를 찾아 Count에 +한다. => first 로만 이루어진 단어

그리고 map에서 (mask | first) 를 찾아 Count에 +한다. => puzzle단어 전체

이 후가 중요한데, mask에서 1을 빼고 mask와 &해준다. => 이를 submask라 하자. (submask = (mask-1)&mask)

다시 map에서 (submask | first) 를 찾아 Count에 + 한다. => 기존 단어에서 가장 작은 알파벳 한개를 뺀 것.

다시 submask에서 1을 빼고 mask와 & 해주고, 해당 과정을 submask가 0이 될때까지 반복해준다.

 

submask를 계속해서 1을 빼주며 mask와 &연산을 해주는 이유는 전체 알파벳 조합에서 부분집합을 만들어내기 위함이다. 이러면 모든 부분집합을 구할 수 있게 된다. (2^6-1)

 

연산을 다시 계산해보면,

처음 word를 저장하는 과정 => 10^5 * 50 => 5*10^6

puzzle mask 생성 => 10^4 * 6 => 6*10^4

submask 순환 => 10^4 * (2^6-1) => 약 6*10^4

 

최대한으로 잡아도 10^6 스케일에서 해결할 수 있게 된다.

앞으로 다른 문제를 풀때 참고해야겠다.

 

전체 풀이 코드

class Solution {
public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        vector<int> ret;
        unordered_map<int, int> m;
        for (string word:words) {
            int b = 0;
            for (char c:word) b|=1<<(c-'a');
            m[b]++;
        }
        for (string puzzle:puzzles) {
            int first = 1<<puzzle[0]-'a', c = m[first], mask = 0;
            for (char ch:puzzle.substr(1)) mask |= 1<<ch-'a';
            for (int sub = mask;sub;sub = (sub-1)&mask)  c += m[sub | first];
            ret.push_back(c);
        }
        return ret;
    }
};