프로그래머스 가사검색 : programmers.co.kr/learn/courses/30/lessons/60060
코딩테스트 연습 - 가사 검색
programmers.co.kr
최근에 백준으로 이분탐색 관련 문제를 조금 풀었었는데 많은 도움이 되었습니다.
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;
}
** 효율성 실행시간
'algorithm > programmers' 카테고리의 다른 글
| programmers 오픈채팅방 (0) | 2020.12.10 |
|---|---|
| Programmers 실패율 (0) | 2020.12.10 |
| Programmers 블록 이동하기 (0) | 2020.12.08 |
| Programmers 디스크 컨트롤러 C++ (0) | 2020.08.20 |
| Programmers 카펫 C++ (0) | 2020.07.03 |
