꽤 재밌는 문제를 풀었다. 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 가 있는데 ...
참고 하자.
다음 문제는 가사검색이라는 프로그래머스 문제에 도전해보겠다.
