[문자열 처리] (3) 문자열 검색 - 프로그래머스 2020 KAKAO BLIND RECRUITMENT > 가사 검색(트라이 알고리즘)

※ 문자열 검색

문자열 검색이란 찾고 싶은 패턴의 문자를 본문 내용에서 어디에 있는지 확인하는 것을 의미합니다.

브루트 포스, 이진 탐색을 이용해서 문자열을 검색하기도 하며,

문자열 검색 알고리즘인 라빈-카프, KMP, 보이어-무어

혹은 트라이 알고리즘 등을 사용하기도 합니다.

이번 포스트에서는 트라이 알고리즘을 이용하여 문제를 풀어보도록 하겠습니다.

※ 트라이 알고리즘

트라이(Trie)는 여러 문자열을 빠르게 찾을 수 있도록 저장하는 자료구조입니다.

이를 이용하면 문자열을 찾을 때 빠르게 검색할 수 있습니다.

다만 빠르게 찾을 수 있는 만큼 저장 공간을 많이 차지합니다. 그 이유는 한 노드에 연결할 수 있는 노드들이 소문자 알파벳의 경우 26개이기 때문입니다.

트라이는 다음과 같이 트리의 모양으로 문자열들을 저장합니다.

트라이

제일 긴 문자열의 길이를 L, 총 문자열들의 수를 M이라 할 때,

- 삽입시 시간복잡도는 가장 긴 문자열의 길이만큼만 삽입하기 때문에 O(L) 입니다.

- 생성시 시간복잡도는 M개에 대해서 트라이 자료구조에 넣는건 가장 긴 문자열 길이(L)만큼 걸려서 O(M*L) 입니다.

- 탐색시 시간복잡도는 가장 긴 문자열의 길이만큼만 탐색하기 때문에 O(L) 입니다.

아래 문제와 함께 트라이 알고리즘을 직접 구현해보겠습니다.

(1) 문제

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

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

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.

가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.

가사 단어 제한사항

• words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
• 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
• 전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
• 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공됩니다.
• 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.

검색 키워드 제한사항

• queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
• 각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
• 전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
• 검색 키워드는 중복될 수도 있습니다.
• 각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
• 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
  • 예를 들어 "??odo", "fro??", "?????"는 가능한 키워드입니다.
  • 반면에 "frodo"('?'가 없음), "fr?do"('?'가 중간에 있음), "?ro??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.

입출력 예

words	queries	result
["frodo", "front", "frost", "frozen", "frame", "kakao"]	["fro??", "????o", "fr???", "fro???", "pro?"]	[3, 2, 4, 1, 0]

입출력 예에 대한 설명

• "fro??"는 "frodo", "front", "frost"에 매치되므로 3입니다.
• "????o"는 "frodo", "kakao"에 매치되므로 2입니다.
• "fr???"는 "frodo", "front", "frost", "frame"에 매치되므로 4입니다.
• "fro???"는 "frozen"에 매치되므로 1입니다.
• "pro?"는 매치되는 가사 단어가 없으므로 0 입니다.

(2) 설명

이 문제는 효율성까지 확인하므로, 문자열 하나씩 모두 확인하면 시간 초과가 걸리게 됩니다.

또한, 검색 키워드의 접두사 아니면 접미사로만 '?'가 주어질 수 있으므로 트라이 알고리즘을 사용하기에 적절합니다.

트라이 알고리즘을 구현하기 위해서는 C++의 경우 생성자, 소멸자, 삽입 함수, 탐색 함수를 구현해야 합니다.

mp 배열을 이용해 문자열의 문자들을 삽입할 때마다 mp[문자열의 길이]에 1을 추가합니다.

예를 들어 "fro"의 경우, f문자 삽입할 때 f문자 노드의 mp[5]+=1, r문자 삽입할 때 r문자 노드의 mp[5]+=1, o문자 삽입할 때 o문자 노드의 mp[5]+=1을 합니다. 이러한 경우에서 "f??"를 찾는 경우, f문자 노드의 mp[5]=1을 가져오므로 결과는 1이 됩니다.

나머지는 일반 트리 연산과 구현 방식이 비슷하니 아래 코드를 참고해주세요.

 

트라이 알고리즘 구현이 완료되었다면 이 문제를 풀기 위해서는 트라이 루트를 2개 만들어야 합니다.

그 이유는 "????o"와 같이 ?가 접두사에 오는 문자열의 경우 트라이 알고리즘을 이용하기 어렵기 때문입니다.

이와 같은 경우는 트라이에 문자열을 저장할 때 트라이 하나를 더 선언하여 문자열을 거꾸로 저장하고 '?'가 접두사에 오는 문자열 역시 거꾸로 탐색하면 됩니다.

즉, '?'가 접두사에 오는 문자열의 경우, 트라이에 문자열 거꾸로 저장, 찾고자 하는 문자열을 거꾸로 탐색하고,

'?'가 접미사에 오는 문자열의 경우, 트라이에 문자열 그대로 저장, 찾고자 하는 문자열을 그대로 탐색합니다.

(3) 풀이

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
 
using namespace std;
 
const int maxx = 26;  // 'a'~'z'까지 개수 26개
 
struct trie {
    bool output;
    trie* go[maxx];
    unordered_map<int,int> mp;
 	
    // 생성자
    trie() {
        fill(go, go + go_max, nullptr);
        output = false;
    }
 	
    // 소멸자
    ~trie() {
        for(int i = 0; i < go_max; i++)
            if(go[i]) delete go[i];
    }
 	
    // 삽입
    void insert(const char *key, int l) {
    	// 문자열 삽입 완료
        if(*key == '\0') {
            output = true;
            return;
        }
        // 문자 인덱스
        int idx = *key - 'a';
        // 문자 추가할 때마다 mp[문자열 길이] 하나씩 추가
        mp[l] += 1;
        // 다음 문자 노드가 없는 경우
        if(!go[idx]) {
            go[idx] = new trie;
        }
        // 다음 문자 삽입
        go[idx]->insert(key + 1, l);
    }
 
 	// 검색
    int find(const char *key, int l) {
    	// 문자열 끝
        if(*key == '\0') return output;
        int ret = 0;
        int idx = *key - 'a';
        
        // 한 문자열 안에서 '?'문자가 나오는 경우 mp[문자열의 길이]를 정답에 합함
        if(*key == '?') {
            ret += mp[l];
        }
        else {
        	// 문자열 존재하지 않음
            if(!go[idx]) return 0;
            // 다음 문자 확인
            ret = go[idx]->find(key + 1, l);
        }
        return ret;
    }
};
 
vector<int> solution(vector<string> w, vector<string> q) {
	// 트라이의 루트 2개 생성
    trie* f = new trie;  // 1번 트라이
    trie* r = new trie;  // 2번 트라이
 
    int wl = w.size(), ql = q.size();
    for(int i = 0; i < wl; i++) {
        string s = w[i];
        // 1번 트라이(문자들 순서 그대로 저장)
        f->insert(&s[0], s.size());
        
        // 2번 트라이(문자들 거꾸로 저장)
        reverse(s.begin(), s.end());
        r->insert(&s[0], s.size());
    }
 
    vector<int> ans(ql);
    for(int i = 0; i < ql; i++){
        string query = q[i];
        
        // 접미사에 '?'가 있는 경우
        if(query[0] != '?'){
            ans[i] = f->find(&query[0], query.size());
        }
        // 접두사에 '?'가 있는 경우
        else {
            reverse(query.begin(), query.end());
            ans[i] = r->find(&query[0], query.size());
        }
    }
    return ans;
}