[2020카카오공채] 가사 검색

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

프로그래머스

단순 문자열끼리 비교하는 방식으로 코드를 짜면 효율성 테스트에서 탈락한다.

따라서 효율적인 알고리즘을 생각해내야 하는 문제인데..

 

처음 내가 짰던 코드는 문자열을 소팅한 후 문자열을 길이별로 저장하는 2차원 배열을 만들어서

배열을 binary search 하는 방식이었다.

이렇게 짜니 효율성 테스트는 간신히 통과했으나 코드가 더럽고 binary search도 직접 구현해야 하는 어려움이 있었다.

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int find_keyword(const vector<string>& words, const vector<int>& words_len, const string &keyword, int x, int y) {
    if (x == y) return x;
    int m = (x + y) / 2;
    int compare = keyword.compare(words[words_len[m]]);
    if (compare > 0) {
        return find_keyword(words, words_len, keyword, m + 1, y);
    }
    else {
        return find_keyword(words, words_len, keyword, x, m);
    }
}

bool check(const string &w, const string &q) {
    for (int i = 0; i < q.length(); i++) {
        if (w[i] != q[i]) {
            return 0;
        }
    }
    return 1;
}

vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;
    int size = words.size();

    // words_inv 만들기
    vector<string> words_inv;
    for (string w : words) {
        string temp;
        for (int i = w.length() - 1; i >= 0; i--) temp += w[i];
        words_inv.push_back(temp);
    }

    // words, words_inv 정렬
    sort(words.begin(), words.end());
    sort(words_inv.begin(), words_inv.end());

    // 문자열 길이별로 저장하는 words_len, words_inv_len 만들기
    vector<int> words_len[10001];
    vector<int> words_inv_len[10001];
    for (int i = 0; i < size; i++) {
        words_len[words[i].length()].push_back(i);
        words_inv_len[words_inv[i].length()].push_back(i);
    }

    for (string q : queries) {
        int cnt = 0;
        int length = q.length();

        // q가 ?로만 구성된 경우
        if (q[0] == '?' && q[length - 1] == '?') {
            cnt = words_len[length].size();
        }
        // q와 일치하는 길이의 단어 없는 경우
        else if (words_len[length].empty()) {
            cnt = 0;
        }
        // ?가 앞에 있는 경우
        else if (q[0] == '?') {
            string temp;
            for (int i = length - 1; i >= 0; i--) {
                temp += q[i];
            }
            q = temp;
            q = q.substr(0, q.find("?"));
            int index = find_keyword(words_inv, words_inv_len[length], q, 0, words_inv_len[length].size() - 1);
            while (index < words_inv_len[length].size()) {
                if (!check(words_inv[words_inv_len[length][index]], q)) break;
                cnt++;
                index++;
            }
        }
        // ?가 뒤에 있는 경우
        else {
            q = q.substr(0, q.find("?"));
            int index = find_keyword(words, words_len[length], q, 0, words_len[length].size() - 1);
            while (index < words_len[length].size()) {
                if (!check(words[words_len[length][index]], q)) break;
                cnt++;
                index++;
            }
        }

        answer.push_back(cnt);
    }

    return answer;
}

 

---

 

해결법은 Trie라는 자료구조를 이용하는 것

https://jason9319.tistory.com/129

[자료구조]트라이(Trie)

Trie란 문자열에 자주 쓰이는 자료구조인데

문자열의 각 글자 하나하나마다 노드가 할당되고 바로 이전 글자에 해당하는 노드의 자식이 되는 구조이다.

그림으로 보면 직관적으로 이해할 수 있다.

 

아무튼 Trie를 이용해 트리를 구성하되

각 노드마다 ordered_map을 만들어서 글자수별 단어의 개수를 저장해둔다.

이렇게 하면 트리를 리프까지 탐색할 필요 없이 쿼리에서 ?가 나왔을 때 노드에 저장된 단어 개수를 반환하면 되므로 효율적이다.

 

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

class Trie {
public:
	Trie* next[26];
	unordered_map<int, int> len;

	Trie() {
		fill(next, next + 26, nullptr);
	}
	~Trie() {
		for (int i = 0; i < 26; i++)
			if (next[i]) delete next[i];
	}

	void insert(const char *key, int length) {
		if (*key == '\0') return;
		else {
			len[length]++;
			int curr = *key - 'a';
			if (next[curr] == nullptr) next[curr] = new Trie();
			next[curr]->insert(key + 1, length);
		}
	}

	int find(const char* key, int length) {
		if (*key == '?') return len[length];
		else {
			int curr = *key - 'a';
			if (next[curr] == nullptr) return 0;
			return next[curr]->find(key + 1, length);
		}
	}
};

vector<int> solution(vector<string> words, vector<string> queries) {
	vector<int> answer;
	Trie root;
	Trie root_inv;

	// Trie에 단어 넣기
	for (string w : words) {
		string inverse;
		for (int i = w.length() - 1; i >= 0; i--) inverse += w[i];
		root.insert(&w[0], w.length());
		root_inv.insert(&inverse[0], inverse.length());
	}

	for (string q : queries) {
		// 쿼리 앞에 ?가 오는 경우
		if (q[0] == '?') {
			string q_inverse;
			for (int i = q.length() - 1; i >= 0; i--) q_inverse += q[i];

			int cnt = root_inv.find(&q_inverse[0], q_inverse.length());
			answer.push_back(cnt);
		}
		// 쿼리 끝에 ?가 오는 경우
		else {
			int cnt = root.find(&q[0], q.length());
			answer.push_back(cnt);
		}
	}

	return answer;
}

 

새로운걸 하나씩 알아가는건 재미있다ㅎ.ㅎ