2020 카카오 신입 개발자 블라인드 채용 1차 코딩 테스트 4번


작성일 : 2019-12-18 02:56:52
조회수 : 148



본문

4번 테스트는 정확성 / 효율성 테스트로 나누어진 문제입니다.

문제를 풀기전 어떤 부분이 효율성으로 올 수 있는지를 먼저 확인해 보았습니다. 단어 개수는 최대 10만개이며, 단 모든 단어 길이의 합은 100만 이하라는 제약이 있는 것을 확인할 수 있고, 쿼리의 개수가 최대 10만개까지 있다고 할 수 있으므로, 여기에서 모든 쿼리에 대해 매번 모든 문자열을 검사하는 $O(n^2)$ 풀이법으로는 점수를 얻을 수 없다는 점을 알 수 있습니다.


그럼 문제를 풀기전 어떻게 단어들을 정리하면 좋을지 생각해봐야 합니다. 잘보면 $?$ 문자열은 prefix혹은 postfix 형태로만 제공되므로, 앞의 문자열까지만 맞으면 뒤에는 어떠한 문자열이 와도 상관이 없는 형태, 즉 앞 또는 뒤로 순차적으로 탐색해볼 수 있는 자료구조를 사용해야 함을 짐작할 수 있습니다. 트라이는 이럴 때 쓰일 수 있는 아주 유용한 자료구조 입니다.


문제를 풀기 위해서 기본적으로 구현할 수 있는 트라이는 아래와 같은 형태입니다.


class Trie {

public:

    int count;

    map<char, Trie> next;


    Trie() {

        count = 0;

    }

};


하나의 문자열에 대해 현재 depth까지 몇개의 node가 접근하는지를 세기 위해 count 변수를 잡고, 다음 char에 대해 다음 depth로 진입하기 위하여 map 형태의 자료구조를 선언하였습니다. 여기서 응용을 해서, ???bc 와 같은 postfix 역시 찾을 수 있도록 양방향 Trie를 구현하였습니다.


class BiTrie {

public:

    int count;

    map<char, BiTrie> prev, next;


    BiTrie() {

        count = 0;

    }

};


이 때 주의해야 할 점이 하나 있습니다. 단어의 길이가 모두 다른 상황에서, 쿼리는 단어의 길이까지 정확하게 같아야 하므로 단어 길이가 다른 Trie는 애초에 접근조차 해서는 안된다는 점입니다. 따라서 단어 길이별로 Trie가 관리될 수 있도록 다음과 같이 선언해 줍니다.


map<char, BiTrie> prefix[10001], postfix[10001];


이제 구현을 해주게 되면 prev, next 를 통해 양방향 Trie를 하나의 객체로 구현할 수 있게 됩니다. 위 Trie에 어떻게 집어넣는 지는 전체적인 소스코드 및 아래 별첨된 prepare method를 통해 확인할 수 있습니다.


void prepare(string &s, BiTrie &b, int pos, int len, bool isPrefix) {

    b.count++;

    if (pos == len-1) return;

    bool f = false;

    if (isPrefix) {

        prepare(s, b.next[s[pos + 1]], pos + 1, len, isPrefix);

    }

    else {

        prepare(s, b.prev[s[len - pos - 2]], pos + 1, len, isPrefix);

    }

}


검색의 로직은 문자열이 나오는 단계에서는 계속 Trie의 다음 depth를 타고 들어가다가, $?$가 나오는 depth에서, 더 이상 다음 depth를 진입하지 않고, 다음 depth에 있는 모든 node의 count를 더해주면 됩니다. 즉, $?$가 나온 시점에서 어떤 노드에 진입을 하더라도 모두 성립되기 때문에 더 이상 진입을 할 필요가 없다는 뜻이 됩니다.


int search(string &s, BiTrie &b, int pos, bool isPrefix) {

    int len = s.length();

    int ret = 0;

    if (isPrefix) {

        if (s[pos] == '?') {

            for (auto it : b.next) ret += it.second.count;

            return ret;

        }

        else {

            if (s[pos + 1] == '?') return search(s, b, pos + 1, isPrefix);

            if (b.next.find(s[pos + 1]) == b.next.end()) return 0;

            return search(s, b.next[s[pos + 1]], pos + 1, isPrefix);

        }

    }

    else {

        if (s[len - pos - 1] == '?') {

            for (auto it : b.prev) ret += it.second.count;

            return ret;

        }

        else {

            if (s[len - pos - 2] == '?') return search(s, b, pos + 1, isPrefix);

            if (b.prev.find(s[len - pos - 2]) == b.prev.end()) return 0;

            return search(s, b.prev[s[len - pos - 2]], pos + 1, isPrefix);

        }

    }

}


여기까지 구현하면 정확성은 쉽게 통과할 수 있습니다. 이제 효율성을 통과하기 위해 어떠한 개선을 할 수 있는지 파악해보겠습니다.


  • 중복된 word가 있으면 Trie에 중복해서 추가해주면 안되므로, string을 관리해주는 map 또는 set 객체를 둡니다.
  • 검색 쿼리도 동일한 쿼리가 올 수 있다고 하였으므로, 한번 검색된 쿼리 역시 결과값을 mapping 하여 이후 중복 처리될 수 있도록 합니다.
  • $????$ 와 같이 모두 $?$로 된 쿼리는 결국 같은 글자 길이의 모든 단어가 정답이므로 단어 길이에 따른 개수도 미리 count 해놓습니다.
이런 점들을 고려하여 전처리 해줄경우 효율성테스트도 75점을 받아 100점으로 통과할 수 있게 됩니다.


#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
using namespace std;
class BiTrie {
public:
    int count;
    map<char, BiTrie> prev, next;

    BiTrie() {
        count = 0;
    }
};
map<char, BiTrie> prefix[10001], postfix[10001];
map<string, int> history;
set<string> dup;
int lencnt[10001];
void prepare(string &s, BiTrie &b, int pos, int len, bool isPrefix) {
    b.count++;
    if (pos == len-1) return;
    bool f = false;
    if (isPrefix) {
        prepare(s, b.next[s[pos + 1]], pos + 1, len, isPrefix);
    }
    else {
        prepare(s, b.prev[s[len - pos - 2]], pos + 1, len, isPrefix);
    }
}
int search(string &s, BiTrie &b, int pos, bool isPrefix) {
    int len = s.length();
    int ret = 0;
    if (isPrefix) {
        if (s[pos] == '?') {
            for (auto it : b.next) ret += it.second.count;
            return ret;
        }
        else {
            if (s[pos + 1] == '?') return search(s, b, pos + 1, isPrefix);
            if (b.next.find(s[pos + 1]) == b.next.end()) return 0;
            return search(s, b.next[s[pos + 1]], pos + 1, isPrefix);
        }
    }
    else {
        if (s[len - pos - 1] == '?') {
            for (auto it : b.prev) ret += it.second.count;
            return ret;
        }
        else {
            if (s[len - pos - 2] == '?') return search(s, b, pos + 1, isPrefix);
            if (b.prev.find(s[len - pos - 2]) == b.prev.end()) return 0;
            return search(s, b.prev[s[len - pos - 2]], pos + 1, isPrefix);
        }
    }
}
vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;

    int len = words.size();
    for (int i = 0; i < len; i++) {
        if (dup.find(words[i]) != dup.end()) continue;
        int wlen = words[i].length();
        dup.insert(words[i]);
        lencnt[wlen]++;
        prepare(words[i], prefix[wlen][words[i][0]], 0, wlen, true);
        prepare(words[i], postfix[wlen][words[i][wlen -1]], 0, wlen, false);
    }

    for (string query : queries) {
        if (history.find(query) != history.end()) {
            answer.push_back(history[query]);
            continue;
        }
        int ans;
        if (query[0] == '?' && query[query.length() - 1] == '?') {
            ans = lencnt[query.length()];
            answer.push_back(ans);
        }
        else if (query[0] != '?') {
            ans = search(query, prefix[query.length()][query[0]], 0, true);
            answer.push_back(ans);
        }
        else {
            ans = search(query, postfix[query.length()][query[query.length() - 1]], 0, false);
            answer.push_back(ans);
        }
        history[query] = ans;
    }

    return answer;
}

2020 카카오 신입 개발자 블라인드 채용 1차 코딩 테스트 4번 - 알고리즘닷컴
취업 대비 알고리즘에서는 다양한 기업들의 기출 문제 및 경향, 풀이 등에 대한 포스팅을 다룹니다.