Number of Matching Subsequences

유승선 ·2024년 1월 16일
0

LeetCode

목록 보기
92/121

꽤 재밌는 문제를 풀었다. input 과 words 벡터가 주어졌을때, input (s) 로 만들 수 있는 단어 개수를 리턴하면 된다.

그런데! 여기서 중요한 점은... 단순하게 s로만 조합하면 되는게 아니라 s가 가지고 있는 원래 순서로 조합할 수 있어야 한다.

"abcde" 가 s일때,
"bb" 는 답이 될 수 없다.

왜냐면 b는 이미 한번 조합이 되었고 더 이상의 b는 없기 때문이다.

"ba" 도 답이 될 수 없다. 조합은 할 수 있지만 b는 a보다 뒤에 있기 대문에 순서가 엉키면 안된다.

이 문제를 보고... 풀기 위해서는 원래 단어의 순서를 무조건 알아야겠다 싶었다.

그렇지만 여기서 s에 나온 캐릭터는 여러번 나올 수 도 있기 떄문에 Map안에 숫자 하나만이 아닌 여러가지 오더를 넣어야 한다.

그렇지만 단어의 순서를 찾을때 한 캐릭터가 많은 반복을 가질 경우.. 벡터의 크기가 커질꺼고 탐색하는데도 오래 걸릴 것이다.

그러면 이건 어떻게 해결해야 할까? Binary Search를 같이 조합해야지 효울 성에서 통과할 수 있다.

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        map<char,vector<int>> hashMap;
        int answer = 0;  
        for(int i = 0; i < s.length(); i++){
            hashMap[s[i]].push_back(i); 
        }

        for(int i = 0; i < words.size(); i++){
            bool flag = 1; 
            int currOrder = -1; 
            string word = words[i]; 
            for(int j=0; j<word.size(); j++){
                char ch = word[j]; 
                if(!hashMap.count(ch)) {flag = 0; break;}
                if(upper_bound(hashMap[ch].begin(), hashMap[ch].end(), currOrder) == hashMap[ch].end()) {flag = 0; break;} 
                currOrder = hashMap[ch][upper_bound(hashMap[ch].begin(), hashMap[ch].end(), currOrder) - hashMap[ch].begin()];
            }
            if(flag) answer++; 
        }

        return answer; 
    }
};

currentOrder를 유지하면서 binary search를 사용해서 내가 탐색하고 싶은 범위만 찾으면 된다. 만약 지금 탐색하려는 캐릭터가 내 currentOrder 보다 적다? 그러면 그 캐릭터는 조합할 수 없다.

이렇게 여러가지 element가 벡터 안에 있을때 이분탐색을 사용할 수 있다니 신기하다.

C++ 에는 lower+bound, upper_bound 가 있는데 ...

참고 하자.

다음 문제는 가사검색이라는 프로그래머스 문제에 도전해보겠다.

profile
성장하는 사람

0개의 댓글