Programmers 가사 검색

프로그래머스 가사검색 : programmers.co.kr/learn/courses/30/lessons/60060

코딩테스트 연습 - 가사 검색

 

최근에 백준으로 이분탐색 관련 문제를 조금 풀었었는데 많은 도움이 되었습니다.

level4 분류에 있던데 '트라이' 자료구조를 사용했을 때 level4에 해당하는 문제같고

이분탐색으로 해결하면 level3 에 해당하는 문제가 아닌가 생각됩니다.

 

솔루션을 간단하게 정리하면 아래와 같습니다.

1. 이분탐색을 위해 words를 정렬해줍니다.

2. queries의 각 문자열 마다 words에 대한 '구간'을 구해줍니다.

3. '구간'탐색은 queries[i]의 각 문자와 인덱스를 가지고 words의 구간에서 lowerbound, upperbound를 찾습니다.

4. upper-lower는 현재 queries의 가능한 모든 경우의 수가 됩니다.

 

좀더 자세한 내용은 코드에 주석을 통하여 설명하였습니다.

코드가 140줄 가량으로 길긴하지만 

사실상 이분탐색을 위한 함수를 복붙한 것이라 solution 함수만 보시면 될 것 같습니다.

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

vector<string> words;
vector<string> reverse_words;
vector<string> queries;

// 배열을 길이 우선, 문자열 순으로 정렬합니다.
bool cmp(string& a, string& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    else if (a.size() == b.size()) return a < b;
}

// 길이에 대한 lower
int lower_start(int s, int e, int len) {
    int m;
    while (s < e) {
        m = (s + e) / 2;
        if (words[m].size() >= len) e = m;
        else s = m + 1;
    }
    return e;
}

// 길이에 대한 upper
int upper_start(int s, int e, int len) {
    int m;
    while (s < e) {
        m = (s + e) / 2;
        if (words[m].size() > len) e = m;
        else s = m + 1;
    }
    return e;
}

// words의 lower
int lowerbound(int s, int e, char ch, int idx) {
    int m;
    while (s < e) {
        m = (s + e) / 2;
        if (words[m][idx] >= ch) e = m;
        else s = m + 1;
    }
    return e;
}

// words의 upper
int upperbound(int s, int e, char ch, int idx) {
    int m;
    while (s < e) {
        m = (s + e) / 2;
        if (words[m][idx] > ch) e = m;
        else s = m + 1;
    }
    return e;
}

// reverse_words의 lower
int reverselowerbound(int s, int e, char ch, int idx) {
    int m;
    while (s < e) {
        m = (s + e) / 2;
        if (reverse_words[m][idx] >= ch) e = m;
        else s = m + 1;
    }
    return e;
}

// reverse_words의 upper
int reverseupperbound(int s, int e, char ch, int idx) {
    int m;
    while (s < e) {
        m = (s + e) / 2;
        if (reverse_words[m][idx] > ch) e = m;
        else s = m + 1;
    }
    return e;
}

vector<int> solution(vector<string> w, vector<string> q) {
    vector<int> answer;
    
    // 함수사용을 위해 전역으로 초기화하였습니다.
    words = w;
    queries = q;
    
    // 접미사부터 탐색해야하는 문자열을 위해
    // words 배열을 역으로 정렬하였습니다.
    reverse_words = words;
    for (int i = 0; i < reverse_words.size(); i++) 
        reverse(reverse_words[i].begin(), reverse_words[i].end());

    // cmp() 기준으로 정렬해줍니다.
    sort(words.begin(), words.end(), cmp);
    sort(reverse_words.begin(), reverse_words.end(), cmp);

    for (int i = 0; i < queries.size(); i++) {
        string str = queries[i];

        // 접두사인 경우
        if (str[0] != '?') {
            // 동일한 길이에 대한 비교를 위한 구간을 탐색합니다.
            int lower = lower_start(0, words.size(), str.size());
            int upper = upper_start(0, words.size(), str.size());

            // 접두사부터 words에 대입해보면서 이분탐색을 실행합니다.
            for (int i = 0; i < str.size(); i++) {
                if (str[i] == '?') break;

                // 현재 lower, upper는 탐색의 기준이 되기때문에 따로 사용합니다. 
                int l = lower;
                int u = upper;
                
                // 현재 문자str[i]의 lower, upper을 찾음
                lower = lowerbound(l, u, str[i], i);
                upper = upperbound(l, u, str[i], i);
            }
            // 구간끝-구간시작 이 가능한 모든 경우입니다.
            answer.push_back(upper - lower);
        }
        // 접미사인 경우(접두사와 같지만 words를 reverse_words로 사용!)
        else if (str[0] == '?') {
            int lower = lower_start(0, reverse_words.size(), str.size());
            int upper = upper_start(0, reverse_words.size(), str.size());
            reverse(str.begin(), str.end());
            for (int i = 0; i < str.size(); i++) {
                if (str[i] == '?') break;
                
                int l = lower;
                int u = upper;
                lower = reverselowerbound(l, u, str[i], i);
                upper = reverseupperbound(l, u, str[i], i);
            }

            answer.push_back(upper - lower);
        }
    }

    return answer;
}

 

 

** 효율성 실행시간