유년

유년

개발자

[SWEA] 3135. 홍준이의 사전놀이 (C++, 라이브러리 X)

Trie 기본문제

풀이

Trie를 구현하고, 각각의 노드에 해당 노드로 시작하는 단어의 개수(cnt)를 저장함.

query함수는 해당 단어를 찾고, cnt를 반환.

해당 단어가 없을 경우 0을 반환

코드 GitHub

struct TrieNode {
    int cnt;
    TrieNode* next[26];

    TrieNode* Alloc() {
        cnt = 0;
        for(int i = 0; i < 26; i++) next[i] = nullptr;
        return this;
    }
} nodes[1000000];
int nodeCnt;
TrieNode head;

void init(void) {
    nodeCnt = 0;
    head.Alloc();
}

void insert(int buffer_size, char *buf) {
    TrieNode* node = &head;
    for(int i = 0; i < buffer_size; i++) {
        int anum = buf[i] - 'a';
        if(!node->next[anum]) node->next[anum] = nodes[nodeCnt++].Alloc();
        node->cnt++;
        node = node->next[anum];
    }
    node->cnt++;
    return;
}

int query(int buffer_size, char *buf) {
    TrieNode* node = &head;
    for(int i = 0; i < buffer_size; i++) {
        int anum = buf[i] - 'a';
        if(!node->next[anum]) return 0;
        node = node->next[anum];
    }
	return node->cnt;
}

댓글남기기