유년

유년

개발자

[SWEA] 12526. 자동완성 (C++, 라이브러리 X)

B형 실전 문제

풀이

Trie를 만들고 카운트(cnt), 밴 여부(ban), 추천 노드(best) 를 저장.

input을 할 때마다 카운트를 1씩 더하고, 부모 노드를 순회하면서 best와 비교 및 교체.

ban을 하면 ban을 true로 해서 추천되지 않도록 하고, 부모 노드를 순회하면서 해당 노드를 best로 갖고 있으면 best를 다시 찾아줌.

recommend를 하면 해당 노드로 찾아가 best를 리턴, best가 ban이거나 cnt가 0일경우 input값을 리턴.

실수

MAX_NODE 값을 넉넉히 줄것. (최대값을 정확히 계산하면 좋겠지만 넉넉히 주는 것이 맘편함!)

ban한 값을 추천하지 않는 로직을 빼먹음 (끝까지 집중해서 코딩할 것)

코드 GitHub

#define MAX_NODE 200000

void mstrcpy(char dst[], const char src[])
{
	int c = 0;
	while ((dst[c] = src[c]) != 0)
		++c;
}

int mstrlen(const char str[])
{
	int ret = 0;
	while (str[ret])
		++ret;
	return ret;
}

int mstrcmp(const char str1[], const char str2[])
{
	int c = 0;
	while (str1[c] != 0 && str1[c] == str2[c])
		++c;
	return str1[c] - str2[c];
}

struct TrieNode {
    char str[20];
    int cnt, time;
    TrieNode *best, *parent, *next[26];
    bool ban;

    TrieNode* Alloc(TrieNode *_parent) {
        str[0] = 0;
        cnt = 0;
        time = 0;
        best = this;
        parent = _parent;
        for(int i = 0; i < 26; i++) next[i] = nullptr;
        ban = false;

        return this;
    }

    void init(char *_str, int _time, bool _ban) {
        if(ban) return;
        mstrcpy(str, _str);
        time = _time;
        cnt = 1;
        ban = _ban;

        return;
    }

    void Add(int _time) {
        time = _time;
        cnt ++;
        return;
    }

    void Ban() {
        ban = true;

        return;
    }
} nodes[MAX_NODE];
int nodeCnt;
TrieNode* head;
int wordCnt;

bool nodecmp(TrieNode* a, TrieNode* b) {
    if(!b) return true;
    if(a->ban) return false;
    if(b->ban) return true;
    if(a->cnt > b->cnt) return true;
    if(a->cnt < b->cnt) return false;
    if(a->time > b->time) return true;
    return false;
}

void init()
{
    nodeCnt = 0;
    wordCnt = 0;
    head = nodes[nodeCnt++].Alloc(nullptr);

    return;
}

void inputWord(char mWord[20])
{
    TrieNode* pivot = head;
    char* a = mWord;

    while(*a) {
        int num = *a++ - 'a';
        if(!pivot->next[num]) 
            pivot->next[num] = nodes[nodeCnt++].Alloc(pivot);
        pivot = pivot->next[num];
    }
    if(pivot->cnt) pivot->Add(wordCnt++);
    else pivot->init(mWord, wordCnt++, false);

    TrieNode* pivot2 = pivot;
    while(pivot2) {
        if(nodecmp(pivot, pivot2->best)) pivot2->best = pivot;
        pivot2 = pivot2->parent;
    }

    return;
}

int recommend(char mUser[20], char mAnswer[20])
{
    TrieNode *pivot = head;
    char *a = mUser;
    while(*a) {
        int num = *a++ - 'a';
        if(!pivot->next[num]) {
            mstrcpy(mAnswer, mUser);
            return mstrlen(mUser);
        }
        pivot = pivot->next[num];
    }
    pivot = pivot->best;
    if(pivot->cnt == 0 || pivot->ban) {
        mstrcpy(mAnswer, mUser);
        return mstrlen(mUser);
    }
    mstrcpy(mAnswer, pivot->str);

	return mstrlen(mAnswer);
}

void banWord(char mWord[20])
{
    TrieNode *pivot = head;
    char *a = mWord;
    while(*a) {
        int num = *a++ - 'a';
        if(!pivot->next[num])
            pivot->next[num] = nodes[nodeCnt++].Alloc(pivot);
        pivot = pivot->next[num];
    }
    pivot->Ban();

    TrieNode *pivot2 = pivot;
    while(pivot2) {
        if(pivot2->best == pivot) {
            for(int i = 0; i < 26; i++) {
                if(pivot2->next[i]) {
                    if(nodecmp(pivot2->next[i]->best, pivot2->best))
                        pivot2->best = pivot2->next[i]->best;
                }
            }
            pivot2 = pivot2->parent;
        } else break;
    }

    return;

}

댓글남기기