반응형
[프로그래머스] 가사 검색 C++
코딩테스트 연습 - 가사 검색
programmers.co.kr
친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "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 입니다.
풀이과정1 => 효율성 테스트 3개 탈락
- 효율성 체크가 있다고 생각해서 나름 대로 생각한 방안이 있었음.
- 물음표가 앞에서부터 시작하는 경우와 뒤에 있는 경우로 나눠서 매칭 여부 판단하는 방안이 바로 그 방안
- 결과는 보기좋게 효율성 테스트 3개 탈락 ㅋㅋ;
코드 => 효율성 테스트 3개 탈락
#include <string>
#include <vector>
using namespace std;
bool isMatched(string word, string query, bool isFrontCase) {
// 글자 길이 틀리면 아예 매치 안됨
if(query.length() != word.length())
return false;
// 물음표가 앞에서부터 시작하는 경우
if(isFrontCase) {
int frontCnt = 0;
// 물음표 갯수 새서
for(int i = 0; i < query.length(); i++) {
if(query[i] == '?') frontCnt++;
}
// 한번에 다 자르고 뒷부분만 맞는지만 체크
if(word.substr(frontCnt) == query.substr(frontCnt))
return true;
}
// 물음표가 앞에서 시작하지 않는 경우
else {
for(int i = 0; i < query.length(); i++) {
// 글자가 다른경우 체크
if(query[i] != word[i]) {
// 물음표 지점에 다와서 다른거였으면 true
if(query[i] == '?') {
return true;
}
// 그냥 다른거였으면 false
return false;
}
}
}
return false;
}
vector<int> solution(vector<string> words, vector<string> queries) {
vector<int> answer;
for(int i = 0; i < queries.size(); i++) {
int cnt = 0;
string query = queries[i];
for(int j = 0; j < words.size(); j++) {
// 앞쪽이 물음표로 시작하는 경우
if(query[0] == '?') {
if(isMatched(words[j], query, true)) {
cnt++;
}
}
// 뒤쪽이 물음표 인 경우
else {
if(isMatched(words[j], query, false)) {
cnt++;
}
}
}
answer.push_back(cnt);
}
return answer;
}풀이과정 2 => 정답
이진탐색으로 풀 수 있을까? 라는 막연한 생각으로 시도하다가 거듭되는 실패에 결국 답을 찾아보기로 함. 찾고보니 실제로 이진탐색으로 풀어낸 방법도 있었고, Trie 알고리즘으로 푸는 방법이 있었음. 근데 Trie 알고리즘은 나중에 잘 써먹을 수 있을까 라는 의구심이 들어서 일단은 활용 가능성이 많은 이진탐색으로 푸는 방법을 적용하기로 함
-
이진탐색은 기본적으로 데이터들이 오름차순으로 정렬이 되어있어야 적용 가능
- 반으로 쪼개는 방식으로 계속해서 탐색 범위를 줄여나가는 것이기 때문에 그 반을 쪼개는 기준이 있어야 하기 때문임. 이해가 가지 않는다면 이진탐색 개념을 학습하고 올 것
-
이진탐색으로 풀더라도 물음표가 앞에서부터 시작하는 케이스와 뒤에서부터 시작하는 케이스 두 개로 나누어 생각했어야 함
- 물음표가 앞에서부터 시작하는 케이스
- 글자를 뒤집고(reverseWords), 물음표가 시작하는 부분부터 'a'를 채워서 lower_bound로 lo 값 찾고, 'z'로 채워서 upper_bound로 hi 값 찾아야 함
- 예를 들어
????o같은 경우,o????로 뒤집고 이 물음표 안에 패턴만 맞으면 되기 때문에oaaaa~ozzzz범위에 있는 word만 찾으면 되기 때문이다.
- 물음표가 앞에서부터 시작하지 않는 케이스
- 위에와 똑같이 생각하면 되는데, 대신에 기존에 있던 words 와 비교하면 됨.
- 물음표가 앞에서부터 시작하는 케이스
-
upper_bound는 찾으려는 key 값을 초과하는 값이 처음 나타나는 위치이고,lower_bound는 찾으려는 Key 값 이상의 값이 처음 나타는 위치 이기 때문에 두 값을 빼주면 words 내지는 reverse_words 안에 있는 글자 중 해당 패턴에 맞는 글자의 개수가 나옴 -
즉, hi - lo 값을 answer 에다 push 해주면 됨
코드 => 정답
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
// 길이가 긴 것은 무조건 뒤쪽으로
// 길이가 같을 경우 오름차순
bool comp(string a, 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;
// 물음표가 앞에서부터 시작하는 케이스를 위해서 words를 뒤집은 데이터도 있어야 함
vector<string> reverseWords = words;
for(int i = 0; i < reverseWords.size(); i++) {
reverse(reverseWords[i].begin(), reverseWords[i].end());
}
// comp 기준 정렬
sort(words.begin(), words.end(), comp);
sort(reverseWords.begin(), reverseWords.end(), comp);
for(int i = 0; i < queries.size(); i++) {
int lo, hi;
int idx;
string query = queries[i];
// ?가 앞에서부터 시작할 때
if(queries[i][0] == '?') {
// 뒤집어서부터 생각
reverse(query.begin(), query.end());
idx = query.find_first_of('?');
// a로 다채움
for(int j = idx; j < query.length(); j++) {
query[j] = 'a';
}
lo = lower_bound(reverseWords.begin(), reverseWords.end(), query, comp) - reverseWords.begin();
for(int j = idx; j < query.length(); j++) {
query[j] = 'z';
}
hi = upper_bound(reverseWords.begin(), reverseWords.end(), query, comp) - reverseWords.begin();
}
// ?가 뒤에서부터 시작할 때
else {
idx = query.find_first_of('?');
for(int j = idx; j < query.length(); j++) {
query[j] = 'a';
}
lo = lower_bound(words.begin(), words.end(), query, comp) - words.begin();
for(int j = idx; j < query.length(); j++) {
query[j] = 'z';
}
hi = upper_bound(words.begin(), words.end(), query, comp) - words.begin();
}
answer.push_back(hi-lo);
}
return answer;
}Reference
반응형
'알고리즘 > 알고리즘 문제 풀이' 카테고리의 다른 글
| [프로래머스] 후보키 c++ (0) | 2020.08.08 |
|---|---|
| [프로그래머스] 기둥과 보 설치 c++ (0) | 2020.07.30 |
| [프로그래머스] 자물쇠와 열쇠 C++ (0) | 2020.07.23 |
| [프로그래머스] 괄호 변환 C++ (0) | 2020.07.20 |
| [프로그래머스] 단어 변환 c++ (0) | 2020.04.14 |