[C++로 풀이] 가사 검색 (트라이 자료구조, 문자열 검색, 이분 탐색) ⭐⭐⭐⭐
카테고리: Programmers
태그: Coding Test Algorithm
📌 가사 검색
난이도 ⭐⭐⭐⭐
🚀 문제
🚀 내 풀이
🔥 트라이 자료구조를 사용한 풀이 ⭕
문자열 집합을 트라이 트리에 저장하고 이를 탐색하면 문제를 해결할 수 있다.
- 우선 입력 크기와 문자열 길이가 상당히 크기 때문에 일일이 비교하는 브루트 포스로는 이 문제의 효율성 테스트를 통과할 수 없을 것이다.
- 트라이를 사용하면 문자열 하나를 어떤 문자열 집합에서 탐색할 때 O(검색하려는 문자열 길이) 시간만 소요되기 때문에 효율적이다.
- 트라이는 트리이기 때문에 중복되는 접두사는 하나의 간선으로서 합쳐지기 때문이다. 즉,
when과what에서whap라는 단어를 브루트 포스로 탐색한다면 4 + 4 = 8 번 비교를 해야 겠지만,when과what를 트라이 트리에 저장해두었다면 하나의 트리를 타고 내려오면 그만이기 때문에whap의 길이인 4 만큼의 시간만 소요되는 것이다!
- 문제에서 가운데 부분 문자열로 매칭 되는 경우는 주어지지 않는다고 하였기 때문에(
fr??o,?oa?같은거 안 주어짐) 접두사만 일치하면 되는 것이므로 손쉽게 트라이만 루트부터 탐색하면 땡이다.- 접두사 구하는 것과 똑같이 접미사를 구하기 위해서는 문자열을 전부 뒤집어서 삽입해 만든 전용 트라이를 따로 만들어 거기서 접두사 구하듯이 순회하면 된다!
일반 트라이와는 다르게 이 문제는 같은 길이의 문자열들만 모아 길이별로 따로 따로 트라이를 만들어야 한다.
왜냐하면 ? 는 딱 한 글자를 가리키기 때문이다. fr??? 는 fr 로 시작하는 5 글자를 뜻하고, fr????? 은 fr 로 시작하는 7 글자를 뜻한다. 이 문제는 특정 접두사 혹은 접미사(문자열 거꾸로 뒤집고 넣으면 접두사 구하는것 과 같아짐)의 개수를 구하는 문제이기 때문에 fr??? 와 fr????? 는 다르게 카운팅 되어야 한다.
그럼 fr 까지의 노드에서 fr???의 개수와 fr?????의 개수 정보를 다 알고 있어야 한다는 이야기다. 트리 특성 상 내려가면서 정보를 업뎃하지 다시 올라가서 정보를 업뎃하기는 힘든데 길이 별로 개수 정보를 따로 관리하려면 단어의 끝까지 도달하여 해당 단어의 개수를 알아낸 후 다시 올라가서 fr 노드로 가 길이를 업데이트 해야한다는 뜻이기도 하다. 뭔가 코드 짜기가 굉장히 까다로울 것 같다..
그래서 그냥 심플하게 위 그림과 같이 길이별로 트라이 트리를 따로 두는 것이다. 트리를 길이별로 여러개 두고, 같은 길이의 문자열들만 같은 트리에 저장한다. fr??? 접두사 패턴을 찾는다면 길이 5 짜리 트라이 트리에서 f를 지나 온 r 노드에 저장된 count를 확인하면 되는 것이다. (fr로 시작하는 7 글자 단어들은 다른 트리에 저장되어 있기 때문에 고려하지 않아도 된다.)
count는 자연스럽게 문자열을 트리에 추가하는 과정에서 문자 하나 하나마다 내려오면서 각 노드마다 1 씩 증가만 시켜주면 된다. what 의 wh 는 각각 1 인 상태였지만, when을 트리에 추가하게되면서 wh 이 1 씩 더 증가된다. 결과적으로 wh 의 count 값은 2 가 되는데, 이는 w 로 시작하는 4 글자짜리 단어가 2 개, wh 로 시작하는 4 글자짜리 단어가 2 개라는 의미가 된다. 중복되는 노드들은 공통된 하나의 노선에 존재하게 되므로 트리를 타고 내려오면서 추가하는 과정에서 그냥 노드마다 1 씩 증가시켜주는 것 만으로도 루트부터 해당 노드까지에 해당하는 접두사로 시작하는 단어의 개수를 자연스럽게 구할 수 있게 된다. 즉, fr 접두사로 시작하는 단어의 개수는 곧 f-r 간선을 지난 횟수와도 같다.
자식 노드들의 주소를 관리하는 방법은 해시맵과 배열이 있다. 아래 풀이 코드에선 배열을 사용하여 관리하였다. 즉, 알파벳 개수와 동일한 26 크기의 배열을 선언하고 이 곳에 저장을 한 것이다. 위 그림은 숫자(0~9) 문자열들을 트라이에 담은 모습인데, 자식 노드들의 주소를 10 크기의 배열로 관리하고 있는 모습이다. 위 그림과 비슷한 자료구조가 된다고 생각하면 된다.
트라이에 관한 더 자세한 설명은 이 포스트를 참고해주세요. 👉 (C++) 문자열 집합 : 트라이 자료구조
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class Trie {
private:
Trie* child[26]; // 자식 노드 주소 배열 (배열로 바로 접근 가능, 인덱스는 소문자 알파벳 순서에 대응)
int count; // 첫 문자부터 해당 노드의 문자까지를 접두사로 가지는 문자들의 개수 (= )
public:
Trie() : child(), count(0) {} // child 는 null 로, count 는 0 으로 초기화
/* 트라이 만들기 */
void Insert(string str) {
Trie* now = this;
for (char ch : str) {
now->count++; // 방문할 때마다 1 증가해주면 됨
if (now->child[ch - 'a'] == nullptr)
now->child[ch - 'a'] = new Trie(); // 없다면 새로 생성
now = now->child[ch - 'a']; // 트리 타고 내려감
}
}
int Search(string str) {
Trie* now = this;
for (char ch : str) {
if (ch == '?') // ? 면 검사하려는 접두사가 끝났다는 것
return now->count; // 현재 방문중인 노드의 count 를 리턴하고 끝내면 된다.
now = now->child[ch - 'a'];
if (now == nullptr) // 트라이의 끝까지 도달 할 때까지도 해당 접두사와 일치하는 것을 만나지 못했다면 해당 접두사로 시작하는 단어는 없는 것
return 0;
}
return -1; // 코드가 정상적이라면 여기에 걸릴 일은 없다.
}
};
Trie TrieRoot[10000]; // 접두사 찾는 길이별 트리들 (문제에서 최대 길이 10000 이라고 제한함)
Trie ReTrieRoot[10000]; // 접미사 찾는 길이별 트리들! 거꾸로 뒤집은 문자열들을 넣어 접두사 찾듯이 찾을 것
vector<int> solution(vector<string> words, vector<string> queries) {
vector<int> answer;
/* 트라이 트리 만들기 (개수 구해놓기) */
for (string str : words) {
TrieRoot[str.length() - 1].Insert(str); // 길이에 맞는 트리에 원래 순서대로 추가
reverse(str.begin(), str.end()); // 문자열 뒤집기
ReTrieRoot[str.length() - 1].Insert(str); // 길이에 맞는 트리에 역순서으로 추가
}
/* 트라이 트리 탐색 */
for (string query : queries) {
if (query[0] != '?') // 접두사 : TrieRoot[str.length() - 1] 트리 탐색
answer.push_back(TrieRoot[query.length() - 1].Search(query));
else { // 접미사 : ReTrieRoot[str.length() - 1] 트리 탐색
reverse(query.begin(), query.end()); // 뒤집기. ??and 가 dna?? 가 되도록
answer.push_back(ReTrieRoot[query.length() - 1].Search(query));
}
}
return answer;
}
이 문제는 처음에 풀지 못했었는데 이 문제가 “트라이 자료구조”를 사용하여 풀 수 있다는 것을 이 유튜브를 통해 알게 되었다. 트라이를 처음 알게 된 문제였다. 그래서 이 문제를 계기로 트라이, KMP, 아호코라식 이렇게 문자열 알고리즘 공부했다.. 코드는 이 유튜브를 참고하였다.
🔥 이분 탐색 풀이 ⭕
이 문제는 이분 탐색으로도 풀 수 있다. 알고리즘 매일매일 블로그 님의 풀이이다. 아이디어가 정말 좋은 풀이라고 느꼈다. 👍👍
fr??? 쿼리는 fr 가 접두사인 5 글자 단어를 뜻한다. 우리는 각각 이 쿼리에 맞는 단어의 개수를 찾아야 한다. fr??? 은 곧 fraaa 이상, frzzz 이하의 범위에 있는 5 글자 짜리 단어들을 찾으면 되는 것이다!
인덱스가 1, 2, 3, 4, 5, 6, 7 이런 범위에서 인덱스 {3, 4, 5} 이 범위의 개수를 구하려면 범위의 끝인 5 보다 큰 1️⃣ 6 에서 3 을 빼거나, 혹은 5 에서 3 보다 작은 2️⃣ 2 를 뺴면 구할 수 있다. 6-3 혹은 5-2 로 개수를 구할 수 있는 것이다. 즉, 구하고자 하는 범위의 처음에 해당하는 위치와 끝에 해당하는 위치의 정보가 필요하다. 이를 이분 탐색으로 구하면 된다!
C++ STL 엔 하한선을 구하는 lower_bound와 상한 선을 구하는 uppder_bound가 API로 마련이 되어 있다. 그러니 5 에서 2 를 빼는 방법보단, 6 의 상한선인 7 에서, 3 의 하한선인 3 을 빼주는 1️⃣ 방법을 선택 하는 것이 편할 것 같다.
lower_bound(Key)는 Key 왈 일치 하거나 혹은 그 이상 의 값 위치를 리턴한다.- 100, 200, 300, 400, 500 에서 350 의 하한선(lower_bound) 은 300 의 위치 3 이 된다. 300 의 하한선은 300 의 위치 3 이 된다.
upper_bound(Key)는 Key 를 초과 하는 것 중 가장 작은 것의 위치를 리턴한다.- 100, 200, 300, 400, 500 에서 300 의 상한선(upper_bound) 은 300 을 초과하는 것 중 가장 작은 값인 400 의 위치 4 가 된다.
lower_bound와는 다르게 Key 를 포함하지 않는다. 초과!
fr???은 곧 fraaa 이상, frzzz 이하의 단어 개수를 구해야 하기에 이분 탐색으로 다음 두 가지를 구하여 두 값을 빼주면 된다. frzzz를 초과하는 문자열의 위치(상한선)에서 fraaa 와 일치하거나 혹은 그 이상의 문자열 위치(하한선)를 구해 빼주면 된다. 즉, fraaa “이상” + frzzz 보다 큰 문자열 중 가장 작은 문자열 “미만” 의 범위가 되겠다.
100, 300, 500, 700, 900 에서 300 이상 800 이하에 해당하는 범위의 개수를 구하고 싶다면 800 의 상한선인 900 의 위치(5) 에서 300 의 하한선인 300 의 위치(2)를 빼주면 구할 수 있다. (5 - 3 = 2 개)
단, 사전 순 정렬은 같은 길이의 문자열 내에서만 적용이 되어야 하기 때문에 (fr???와 fr??????의 개수는 다르게 카운팅 되어야 함) 비교 함수를 따로 만들어 같은 길이를 가진 범위에서만 사전 순으로 판단할 수 있도록 정렬 기준을 적용시켜 주어야 한다. 예를 들어 “zzz”가 “abcde” 보다 더 앞에 와야 한다고, “abcde” 보다 작은 값이라고 판단하여 상한선, 하한선을 구할 수 있도록 해야 한다. 오직 사전 순으로만 판별하면 “abcd” 가 “azz” 보다 작은 값이기 때문에 길이에 상관없이 상한선, 하한선을 구하게 된다.
- A 이상 B 미만의 범위에 해당하는 개수 👉 B - A
- B =
frzzz의 상한선의 위치 (frzzz 보다 큰 값 중 가장 작은 값) - A =
fraaa의 하한선의 위치 (fraaa 이상인 값. fraaa 를 포함할 수도 있음) - B - A :
fr로 시작하는 문자열들의 총 개수 (길이 별로 정렬되어 있다는 전제 하에)
- B =
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
/* 비교함수! 같은 길이에서만 사전 순 정렬할 수 있도록 한다. zzz bbcd bbcf abcdefg 요런식으로 정렬되도록 */
bool comp(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> solution(vector<string> words, vector<string> queries) {
vector<int> answer;
vector<string> rwords(words);
for (int i = 0; i < rwords.size(); i++)
reverse(rwords[i].begin(), rwords[i].end());
/* 이진 탐색 전 정렬 필수 */
sort(words.begin(), words.end(), comp);
sort(rwords.begin(), rwords.end(), comp);
for (string query : queries) {
if (query[0] != '?') { // 접두사
/* fr??? 꼴 하한선 위치 구하기 -> fraaa 로 변환 */
string start(query);
for (int i = 0; i < start.length(); ++i)
if (start[i] == '?') // ?를 모두 a 로 바꾸기
start[i] = 'a';
auto start_ptr = lower_bound(words.begin(), words.end(), start, comp); // fraaa 하한선 위치. 비교 함수를 적용하여 같은 길이 내에서 하한선을 찾도록 한다
string end(query);
for (int i = 0; i < end.length(); ++i)
if (end[i] == '?') // ?를 모두 z 로 바꾸기
end[i] = 'z';
auto end_ptr = upper_bound(words.begin(), words.end(), end, comp); // frzzz 상한선 위치. 비교 함수를 적용하여 같은 길이 내에서 상한선을 찾도록 한다
answer.push_back(end_ptr - start_ptr);
}
else { // 접미사
reverse(query.begin(), query.end()); // 쿼리문도 뒤집기! 뒤집고 나서 접두사 구하듯이 구하면 된다.
string start(query);
for (int i = 0; i < start.length(); ++i)
if (start[i] == '?')
start[i] = 'a';
auto start_ptr = lower_bound(rwords.begin(), rwords.end(), start, comp);
string end(query);
for (int i = 0; i < end.length(); ++i)
if (end[i] == '?')
end[i] = 'z';
auto end_ptr = upper_bound(rwords.begin(), rwords.end(), end, comp);
answer.push_back(end_ptr - start_ptr);
}
}
return answer;
}
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기