[프로그래머스 Lv4] : 가사 검색

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/60060

프로그래머스

키워드가 담긴 배열이 주어졌을 때, 각 키워드 별로 매치된 단어가 몇 개인지 리턴하자.

 

오답

 나는 단어와 키워드를 직접 비교를 하는 방식을 선택했다.

먼제 단어를 시작하는 알파벳, 단어의 길이를 기준으로 분류했다.

단어의 길이와 키워드의 길이가 일치하지 않으면 비교할 필요가 없기 때문이다.

 

이때 키워드에 물음표가 뒤에 붙어있다면, 문자를 앞에서부터 비교하고 물음표가 나오는 순간부터는 비교를 그만했다.

반대로 물음표가 앞에 붙어있다면, 문자를 뒤에서부터 비교해서 물음표가 나오기 전까지 비교했다.

이렇게해서 매치되는 단어의 수를 리턴하도록 했다.

 

그리고 중복된 키워드가 있을 수 있다는 조건이 있기 때문에, 키워드별로 인덱스를 부여해서 키워드별로 매치된 단어의 개수를 저장해두었다.

만약 해당 키워드의 매치된 단어의 수가 이미 저장되어있으면 그 값을 꺼내서 리턴하도록 함수를 작성했다.

 

이렇게 작성한 코드가 아래와 같다.

오답 코드

#include <bits/stdc++.h>
using namespace std;
map<string, int> Index;
int Count[100000 + 5];
vector<string> start_with[26][100000 + 1];
vector<string> end_with[26][100000 + 1];
 
int Find(vector<string> words, string str){
    if(Count[Index[str]] != -1) //이미 했던 키워드라면
        return Count[Index[str]];
    
    if(str[0] == '?' && str[str.length() - 1] == '?')
        return words.size();
    
    if(str[0] == '?'){
        //뒤에서부터 비교
        int cnt = 0;
        for(auto Cmp : end_with[str[str.length() - 1] - 'a'][str.length()]){
            bool chk = true;
            for(int i = str.length() - 1; i > 0; i--){
                if(str[i] == '?')
                    break;
                if(str[i] != Cmp[i]){
                    chk = false;
                    break;
                }
            }
            if(chk)
                cnt++;
        }
        Count[Index[str]] = cnt;
        return cnt;
    }
    else{
        //앞에서부터 비교
        int cnt = 0;
        for(auto Cmp : start_with[str[0]- 'a'][str.length()]){
            bool chk = true;
            for(int i = 0; i<str.length(); i++){
                if(str[i] == '?')
                    break;
                if(str[i] != Cmp[i]){
                    chk = false;
                    break;
                }
            }
            if(chk)
                cnt++;
            else{
                if(cnt)
                    break;
            }
        }
        Count[Index[str]] = cnt;
        return cnt;
    }
}
 
vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;
    memset(Count, -1, sizeof(Count));
    sort(words.begin(), words.end());
    
    for(auto str : words){
        start_with[str[0] - 'a'][str.length()].push_back(str);
        end_with[str[str.length() - 1] - 'a'][str.length()].push_back(str);
    }
    
    int idx = 0;
    for(auto str : queries){
        if(Index.find(str) == Index.end()){
            Index.insert({str, idx++});
        }
    }
    
    for(auto str : queries)
        answer.push_back(Find(words, str));
    
    return answer;
}

모든 단어를 직접 비교해야하기 때문에 단어의 양이 많아질수록, 단어의 길이가 길어질수록 시간이 오래걸린다는 단점이 있다.

그래서 효율성테스트 1,2,3에서 시간초과를 받았다.

 

 풀이

조금 더 효율적으로 비교할 필요가 있었다.

이분탐색을 이용해면 된다고 하는데, 문자열에서 이분탐색을 어떻게 이용하는지 도저히 감이 잡히지 않아서 오늘도 고수분들의 아이디어를 참고했다.

 

오늘도 "공부하는 식빵맘" 님의 해설을 참고했다.

 

이분탐색을 직접적으로 이용하는 것이 아니라, upper_bound와 lower_bound를 이용하는 것이었다. 아이디어가 정말 참신한 것 같다.

 

만약 키워드가 "fro??" 라면 "frost", "frodo", "froze" 등등 "fro"로 시작하는 5글자 단어면 모두 매치가 된다.

사전순으로 했을 때, "fro"로 시작하는 5글자 단어중에 가장 첫번째 단어는 "froaa"가 될 것이다.

그리고 가장 마지막 단어는 "frozz"가 될 것이다.

우리는 "froaa"와 "frozz" 사이에 있는 단어의 개수를 찾아주면 된다.

 

상한선은 upper_bound를 이용해서 "frozz"보다 큰 문자의 인덱스로 설정한다.

하한선은 lower_bound를 이용해서 처음으로 "froaa"보다 크거나 같은 문자의 인덱스로 설정한다.

상한선과 하한선 사이에 있는 문자들이 "fro??"로 검색가능한 단어들이다.

 

키워드가 "????o" 처럼 물음표로 시작하는 경우에는 말이 달라진다.

앞의 예시처럼 "aaaao"와 "zzzzo" 사이에 있는 단어들이라고 하면

조건에 맞지않는 "froze"와 같은 단어도 포함이 된다.

이 경우에는 모든 단어와 키워드를 뒤집어서 앞선 예시와 똑같이 되도록 한다.

  "o????"로 뒤집고 단어도 "kakao" -> "oakak", "frodo" -> "odorf" 로 뒤집으면

upper_bound, lower_bound를 이용해서 상한선 하한선을 잡을 수 있다.

이때 단어를 뒤집는 것은 reverse함수를 이용하면 된다.

이번 문제를 통해서 reverse라는 함수가 있다는 것을 처음 알게되었다.

 

코드 작성

#include <bits/stdc++.h>
using namespace std;
 
bool cmp(const string& a, const string& b){
    if(a.length() < b.length())
        return true;
    else if(a.length() == b.length()){
        if(a < b)
            return true;
    }
    return false;
}
 
vector<int> Find(vector<string> words, vector<string> reversed, vector<string> queries){
    vector<int> ans;
    for(auto key_word : queries){
        if(key_word[0] == '?'){ //맨 앞에 물음표
            reverse(key_word.begin(), key_word.end());
            string from = "";
            string to = "";
            for(int i = 0; i<key_word.length(); i++){
                if(key_word[i] == '?'){
                    from += "a";
                    to += "z";
                }
                else{
                    from += key_word[i];
                    to += key_word[i];
                }
            }
            ans.push_back(upper_bound(reversed.begin(), reversed.end(), to, cmp)
                - lower_bound(reversed.begin(), reversed.end(), from, cmp));
        }
        else if(key_word[key_word.length() - 1] == '?'){
            string from = "";
            string to = "";
            for(int i = 0; i<key_word.length(); i++){
                if(key_word[i] == '?'){
                    from += "a";
                    to += "z";
                }
                else{
                    from += key_word[i];
                    to += key_word[i];
                }
            }
            ans.push_back(upper_bound(words.begin(), words.end(), to, cmp)
                - lower_bound(words.begin(), words.end(), from, cmp));
        }
    }
    return ans;
}
 
vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;
    vector<string> reversed(words);
    
    for(int i = 0; i<reversed.size(); i++)
        reverse(reversed[i].begin(), reversed[i].end());
    
    sort(words.begin(), words.end(), cmp);
    sort(reversed.begin(), reversed.end(), cmp);
    
    answer = Find(words, reversed, queries);
    return answer;
}

 

단순히 sort함수를 이용하게되면 사전순으로만 정렬하기 때문에 문자열의 길이에 상관없이 사전순으로 정렬이 된다.

비교함수를 따로 선언 해주어서 문자열의 길이가 긴 문자열이 반드시 뒤로 가도록 해준다.

 

upper_bound와 lower_bound를 이런식으로도 이용할 수 있다는 것을 한 수 배웠다.

물음표를 a와 z로 전환하는 아이디어는 너무 기발하다.