[프로그래머스][C++] 2020 KAKAO: 가사 검색

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/60060

 

오랜만에 문제다운 문제를 풀고 있습니다. 그동안 좀 쉬었습니다. 몸도 아팠고 의욕도 없고 그랬네요. 으~ 다시 해봐야죠.

 

이 문제는 정확성 테스트는 아무렇게나 짜도 통과될겁니다. 별로 어렵지 않고요

문제가 효율성 테스트인데, 문자열을 정렬한 뒤 이분탐색하거나 트라이를 만드는 것이 정답입니다.

트라이로 풀려면 일단 단어들의 트라이를 두개 만들어줘야 됩니다. 그냥 트라이와 단어 거꾸로 돌린 트라이를 만들어줘야됩니다. 왜냐면 와일드카드 문자가 앞, 뒤에 나올 수 있는데 abc?? 이런식으로 와일드카드가 뒤에 나오게 해야 개수를 셀 수 있기 때문입니다.

#include <bits/stdc++.h>

using namespace std;

struct trie_node {
    map<char, trie_node> children;
    bool terminal;

    trie_node() : terminal(false) {}
};

void trie_insert(trie_node& root, const string& s) {
    trie_node* curr = &root;

    for (const auto& c : s) {
        if (curr->children.find(c) == curr->children.end())
            curr->children[c] = trie_node();

        curr = &(curr->children[c]);
    }

    curr->terminal = true;
}

bool trie_search(const trie_node& root, const string& s) {
    const trie_node* curr = &root;

    for (const auto& c : s) {
        if (curr->children.find(c) == curr->children.end())
            return false;

        curr = &(curr->children.at(c));
    }

    return curr->terminal;
}

void dfs(const trie_node& root, const int& depth, const int& max_depth, int& counter) {
    if (depth == max_depth) {
        if (root.terminal)
            ++counter;

        return;
    }

    for (const auto& [ign, child] : root.children) {
        dfs(child, depth + 1, max_depth, counter);
    }
}

// pattern: ex) fro?? (O), ??ost (X)
// question mark should be exist at back of the string
int trie_count_pattern(const trie_node& root, const string& pattern) {
    int counter = 0;
    const trie_node* curr = &root;

    // move before '?'
    for (const auto& c : pattern) {
        if (c == '?') break;

        if (curr->children.find(c) == curr->children.end())
            return 0;

        curr = &(curr->children.at(c));
    }

    // the number of '?'
    auto qs = count(pattern.begin(), pattern.end(), '?');

    // count terminal nodes below current node
    // with adequate depth (= the number of '?')
    dfs(*curr, 0, qs, counter);

    return counter;
}

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

    // make trie (orig, reverse)
    trie_node trie_orig, trie_rev;
    for (const auto& s : words) {
        auto s_rev(s);
        reverse(s_rev.begin(), s_rev.end());

        trie_insert(trie_orig, s);
        trie_insert(trie_rev, s_rev);
    }

    // check
    for (const auto& query : queries) {
        if (query.front() == '?') {
            auto q_rev = query;
            reverse(q_rev.begin(), q_rev.end());
            answer.push_back(trie_count_pattern(trie_rev, q_rev));
        }
        else {
            answer.push_back(trie_count_pattern(trie_orig, query));
        }
    }

    return answer;
}

지금 이건 맞는 코드는 아닙니다. 효율성 테스트케이스 4, 5번만 통과네요. 이유가 뭘까요.. 트라이를 맵으로 짜서 그런가, 아니면 dfs 때문인가 흐음..

헌혈하고 와서 좀 생각해봐야겠습니다. 코딩을 한 3주만에 했더니 새롭네요.

 

+ 일단 위에거가 속도가 안나오는 이유는 ? 전까지 트라이에 들어간 다음 dfs로 단말노드(leaf, terminal node) 개수를 세서 그런 거였습니다. 느릴 수밖에 없죠

그럼 어떻게 하느냐.. 트라이에 단어 넣을 때 각 노드마다 카운터를 둬서 +1 합니다.

근데 그러면 fro??랑 fro??? 구분이 안됩니다. 그래서 단어가 최대 만글자니까 10000개짜리 트라이 배열을 좀 만들어줘야 합니다. (좀 그지같네요)

#include <bits/stdc++.h>
using namespace std;


struct trie_node {
	trie_node* children[26];
	int counter;

	trie_node(): counter(0) {
		fill(begin(children), end(children), nullptr);
	}

	~trie_node() {
		for (auto& p : children) {
			if (p)
				delete p;
		}
	}
};

trie_node trie_orig[10000], trie_rev[10000];	// jesus

void trie_insert(trie_node& root, const string& s) {
	trie_node* curr = &root;
	++curr->counter;

	for (const auto& c : s) {
		if (curr->children[c - 'a'] == nullptr)
			curr->children[c - 'a'] = new trie_node();

		curr = curr->children[c - 'a'];
		++curr->counter;
	}
}

// pattern: ex) fro?? (O), ??ost (X)
// question mark should be exist at back of the string
int trie_count_pattern(const trie_node& root, const string& pattern) {
	const trie_node* curr = &root;

	// move before '?'
	for (const auto& c : pattern) {
		if (c == '?') break;

		if (curr->children[c - 'a'] == nullptr)
			return 0;

		curr = curr->children[c - 'a'];
	}

	return curr->counter;
}

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

	// make trie (orig, reverse)
	for (const auto& s : words) {
		auto s_rev(s);
		reverse(s_rev.begin(), s_rev.end());

		trie_insert(trie_orig[s.size()-1], s);
		trie_insert(trie_rev[s.size()-1], s_rev);
	}

	// check
	for (const auto& qq : queries) {
		if (qq.front() == '?') {
			auto q_rev = qq;
			reverse(q_rev.begin(), q_rev.end());
			answer.push_back(trie_count_pattern(trie_rev[qq.size()-1], q_rev));
		}
		else {
			answer.push_back(trie_count_pattern(trie_orig[qq.size()-1], qq));
		}
	}

	return answer;
}

뭐 그렇게 하면 착착 풀립니다.

중간에 자꾸 효율성 테스트케이스 3이 틀리길래 왜그럴까 고민고민을 했더니 쿼리가 전부 물음표일때 루트의 카운터를 체크하게 되는데 루트는 카운터 체크를 안했더라고요. 그거만 바꿔줬더니 잘 통과됩니다.