항해//프로그래머스 60060// 가사 검색/c++//

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

프로그래머스

 

내가 처음 낸 코드 

정규식regex 사용해서 풀어나갔는데

아무래도 속도(효율성) 측면에서 부족한듯 하다.

#include <iostream>
#include<vector>
#include<regex>
#include<string>
using namespace std;

vector<int> solution(vector<string>& words, vector<string>& queries)
{
	vector<int> answer;
	
	for (auto& query : queries)
	{
		string regexPattern = query;
		for (char& c : regexPattern)
		{
			if(c=='?')c = '.';
		}

		regex r(regexPattern);//정규식 객체 생성
		int count = 0;
		for (const auto& word : words)
		{
			if (regex_match(word, r)) //정규식객체가 비교대상인되는 word배열과매칭이되면
            {
            	++count;//카운트를 늘림
            }
		}
		answer.push_back(count);
	}
	
	return answer;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<string> words;
	vector<string> key;

	cout << "how many words and keywords to type? " << endl;
	int n,m ;
	cin >> n>>m;
	words.resize(n);
	key.resize(m);
	cout << "type the words" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> words[i];	
	}
	//for (auto a : words) cout << a << " ";

	cout << " type keywords :" << endl;
	for (int i = 0; i < m; i++)
	{
		cin >> key[i];
	}
	//for (auto a : key) cout << a << " ";

	vector<int>ans=solution(words, key);
	for (auto a : ans) cout << a << " ";

	return 0;
}

 

#include <iostream>
#include<vector>
#include<regex>
#include<string>
using namespace std;

vector<int> solution(vector<string> words, vector<string> queries)
{
	vector<int> answer;
	
	for (auto& query : queries)
	{
		string regexPattern = query;
		for (char& c : regexPattern)
		{
			if(c=='?')c = '.';
		}

		regex r(regexPattern);
		int count = 0;
		for (const auto& word : words)
		{
			if (regex_match(word, r)) ++count;
		}
		answer.push_back(count);
	}
	
	return answer;
}

 

대략 시간 복잡도가

O(Q * W * L)

Q 쿼리 수= for (auto& query : queries)

W = 단어 수 for (const auto& word : words) { // O(W) - W는 단어의 수 regex_match(word, r) 

L = 문자열의 길이 for (char& c : regexPattern) { ... }

 

이를 실제 상황에 대입해보면:

• Q (쿼리 수) = 100
• W (단어 수) = 1000
• L (평균 문자열 길이) = 10

이라면, 최악의 경우 약 1,000,000번의 연산이 필요하다는 의미이다.

대규모 데이터의 경우에는 엄청난 연산이 필요하기 때문에 효율성은 ㅜㅜ 아래와 같이 마구 마구 떨어지는 ...

 

 

 

효율성 안녕~~~~

 

결국 이분탐색으로 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;


vector<int> solution(const vector<string>& words, const vector<string>& queries) 
{
   //?가 앞에 있는 쿼리를 효과적으로 처리하기 위해 reversedWordGroups활용(eg. eppl? vs epplA)
    vector<vector<string>> wordGroups(10001), reversedWordGroups(10001);
    for (const auto& word : words) 
    {
        //쿼리의 길이와 단어의 길이가 다르면 절대 매칭되지 않기 때문에 사이즈별로 나눠 탐색대상을 줄임
        wordGroups[word.size()].push_back(word);
        string reversedWord = word;
        reverse(reversedWord.begin(), reversedWord.end());
        reversedWordGroups[word.size()].push_back(reversedWord);//사이즈별로 뒤집어서 저장
    }

    //binary search는 정렬이된 배열에서만 정상작동!!!
    for (auto& group : wordGroups) sort(group.begin(), group.end());
    for (auto& group : reversedWordGroups) sort(group.begin(), group.end());

    vector<int> answer;
    for (const auto& query : queries) 
    {
        int len = query.size();
        if (wordGroups[len].empty()) 
        {  
        // 해당 길이의 단어가 없는 경우
            answer.push_back(0);
            continue;
        }

        // 물음표 위치 확인
        if (query[0] != '?') 
        {  
        // 물음표가 뒤에 있는 경우
            string start = query;//검색 시작점
            string end = query;
            // 쿼리의 물음표(?)를 a(최소값)와 z(최대값)으로 치환하여 검색 범위를 확정
            replace(start.begin(), start.end(), '?', 'a'); //예: "app??" → start = "appaa"
            replace(end.begin(), end.end(), '?', 'z');     // 최대값 예:end = "appzz"
            
            //end(예: "appzz")보다 큰 첫 번째 위치 - start(예: "appaa")보다 크거나 같은 첫 번째 위치
            int count = upper_bound(wordGroups[len].begin(), wordGroups[len].end(), end) -
                        lower_bound(wordGroups[len].begin(), wordGroups[len].end(), start);
            answer.push_back(count);
        }
        else 
        {  
        // 물음표가 앞에 있는 경우
            string reversedQuery = query;
            reverse(reversedQuery.begin(), reversedQuery.end());//쿼리도 귀집기 ??ple->elp??
            string start = reversedQuery;
            string end = reversedQuery;
            replace(start.begin(), start.end(), '?', 'a');  //??ple->aaple
            replace(end.begin(), end.end(), '?', 'z');      //??ple->zzple
            
            int count = upper_bound(reversedWordGroups[len].begin(), reversedWordGroups[len].end(), end) -
                        lower_bound(reversedWordGroups[len].begin(), reversedWordGroups[len].end(), start);
            answer.push_back(count);
        }
    }

    return answer;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<string> words(n);
    vector<string> queries(m);

    for (int i = 0; i < n; i++) cin >> words[i];
    for (int i = 0; i < m; i++) cin >> queries[i];

    vector<int> result = solution(words, queries);
    for (int i : result) cout << i << "\n";

    return 0;
}

 

물음표가 뒤에 있을 때 예제

• 단어 리스트: {"apple", "apply", "appzz", "banana"}
• 쿼리: "app??"
  • start = "appaa", end = "appzz"
• 이분 탐색 결과:
  • lower_bound(..., "appaa") → "apple"의 위치 반환.
  • upper_bound(..., "appzz") → "banana"의 위치 반환.
  • 결과: upper_bound - lower_bound = 3-0=3 ("apple", "apply","appzz")

물음표가 앞에 있을 때 예제

• 뒤집어진 단어 리스트: {"elpaa", "elpba", "elppa", "elppz"}
• 쿼리: "elp??"
  • start = "elpaa", end = "elpzz"
• 이분 탐색 결과:
  • lower_bound(..., "elpaa") → "elpaa" 위치 반환.
  • upper_bound(..., "elpzz") → 리스트의 끝 반환.
  • 결과: upper_bound - lower_bound = 4-0=4(모든 리스트내 단어가 포함)

 

현재 이분탐색 방식:

• 초기 정렬: O(W * log W)
• 각 쿼리 처리: O(Q * log W)
• 총 시간복잡도: O(W * log W + Q * log W)

 

이전 정규식 방식

•  O(Q * W * L)의 시간 복잡도를 가짐

실제 예시로 비교하자면 (W=1000, Q=100, L=10 일 때):

• 이분탐색: 약 1000 * 10 + 100 * 10 = 11,000번 연산
• 정규식: 약 100 * 1000 * 10 = 1,000,000번 연산

이분탐색법이 대략 100배 효율적이다~!

---

주요 아이디어

1. 단어 길이별로 그룹화
   쿼리와 단어의 길이가 다르면 절대 매칭되지 않으므로, 단어를 길이별로 그룹화하여 검색 대상을 줄입니다.
   wordGroups와 reversedWordGroups는 각각 원래 단어와 뒤집힌 단어를 저장합니다.
   • wordGroups: 길이별로 단어를 그룹화
   • reversedWordGroups: 뒤집힌 단어를 길이별로 그룹화
2. 정렬을 통한 이진 탐색
   그룹화된 단어를 정렬하여 이진 탐색을 사용할 수 있게 준비합니다.
   쿼리의 검색 범위를 정렬된 배열에서 상하한 경계를 통해 찾습니다.
3. 물음표(?) 처리
   • 물음표가 뒤에 있을 경우: 해당 단어는 start와 end로 정의된 범위 안에 존재합니다.
   • 물음표가 앞에 있을 경우: 쿼리와 단어를 뒤집어 처리한 뒤, start와 end 범위를 계산합니다.

---

코드 설명

1. 단어와 쿼리 준비
   • 각 단어의 길이를 기준으로 wordGroups와 reversedWordGroups에 저장합니다.
   • 물음표가 앞에 있는 경우를 처리하기 위해 단어를 뒤집어서 저장합니다.
2. vector<vector<string>> wordGroups(10001), reversedWordGroups(10001); for (const auto& word : words) { wordGroups[word.size()].push_back(word); string reversedWord = word; reverse(reversedWord.begin(), reversedWord.end()); reversedWordGroups[word.size()].push_back(reversedWord); }
3. 정렬
   • 이진 탐색을 사용할 수 있도록 각 그룹을 정렬합니다.
4. for (auto& group : wordGroups) sort(group.begin(), group.end()); for (auto& group : reversedWordGroups) sort(group.begin(), group.end());
5. 쿼리 처리
   • 쿼리를 하나씩 처리하며 물음표의 위치에 따라 나눕니다.
   (1) 물음표가 뒤에 있는 경우
   • 쿼리의 물음표를 'a'와 'z'로 바꿔 검색 범위를 정의합니다.
   • lower_bound: 시작 범위 (쿼리 문자열의 최소값)
   • upper_bound: 끝 범위 (쿼리 문자열의 최대값)
   • 두 값의 차가 해당 쿼리에 매칭되는 단어의 개수입니다.
   (2) 물음표가 앞에 있는 경우
   • 쿼리와 단어를 뒤집어서 처리합니다.
   • 뒤집힌 단어로 동일한 방식으로 검색 범위를 정의합니다.
6. string reversedQuery = query; reverse(reversedQuery.begin(), reversedQuery.end()); string start = reversedQuery; string end = reversedQuery; replace(start.begin(), start.end(), '?', 'a'); replace(end.begin(), end.end(), '?', 'z'); int count = upper_bound(reversedWordGroups[len].begin(), reversedWordGroups[len].end(), end) - lower_bound(reversedWordGroups[len].begin(), reversedWordGroups[len].end(), start); answer.push_back(count);
7. string start = query; string end = query; replace(start.begin(), start.end(), '?', 'a'); replace(end.begin(), end.end(), '?', 'z'); int count = upper_bound(wordGroups[len].begin(), wordGroups[len].end(), end) - lower_bound(wordGroups[len].begin(), wordGroups[len].end(), start); answer.push_back(count);
8. 결과 반환
   • 각 쿼리의 결과를 answer에 저장하고 최종적으로 반환합니다.

---

시간 복잡도

1. 단어와 쿼리의 전처리
   • 단어를 그룹화하고 정렬: O(Wlog⁡W)O(W \log W), WW는 단어의 총 개수.
2. 각 쿼리 처리
   • 이진 탐색: O(log⁡W)O(\log W) (길이별로 정렬된 단어 리스트에서 탐색).
   • 쿼리 개수를 QQ라 할 때 Q×log⁡WQ \times \log W만큼 처리.

따라서, 전체 시간 복잡도는 O(Wlog⁡W+Qlog⁡W)O(W \log W + Q \log W)입니다.

---

예제 입력/출력

입력

vector<string> words = {"frodo", "front", "frost", "frozen", "frame", "kakao"};
vector<string> queries = {"fro??", "????o", "fr???", "fro???", "pro?"};

출력

vector<int> result = solution(words, queries);
// result: {3, 2, 4, 1, 0}

해석:

1. "fro??": 길이가 5인 단어 중 fro로 시작하는 단어 → 3개 (frodo, front, frost)
2. "????o": 길이가 5인 단어 중 o로 끝나는 단어 → 2개 (frodo, kakao)
3. "fr???": 길이가 5인 단어 중 fr로 시작하는 단어 → 4개 (frodo, front, frost, frame)
4. "fro???": 길이가 6인 단어 중 fro로 시작하는 단어 → 1개 (frozen)
5. "pro?": 길이가 4인 단어 중 pro로 시작하는 단어 → 0개.