[SWEA] 3135 홍준이의 사전놀이

 

트라이 기본 문제다.

트라이 짜는법을 마지막으로 정적으로 배웠기 때문에 정적트라이를 이용했다!

 

문제를 푸는 방법은 간단하다

트라이를 만들고 cnt배열을 만들어서 지나가는 정점마다 cnt를 올려주면 된다

그럼 내가 어떤 지점에서 시작한다고 할 때 그 수만큼 cnt가 올라갈 것 이다

 

근데 문제는 초기화가..! 문제였다

정적으로 잡기 때문에 노드의 수를 미리 max로 두고 시작한다

여기서는 100000개의 쿼리 X 10자리수 X 알파벳 26개 다

 

근데 바보같이 초기화 하는 부분에서 max 크기만큼 모든배열을 계속 초기화했다

시간초과가 정확히 30번 났다

 

혹시 오타가 났나 계속 다시 짰는데 문제는 초기화였다

생각해보면 초기화는 내가 사용한 정점까지만 해주면 된다

trie_cnt에 저장해놨기 때문에 딱 이만큼만 해주면 시간안에 너어어무 여유롭게 들어온다!

 

소스코드

#include <stdio.h>
#include <iostream>
using namespace std;
 
const int N = 100010 * 12;
const int M = 27;
 
int trie[N+1][M+1];
int cnt[N + 1];
int trie_cnt = 1;
 
void init(void) {
    for (int i = 0; i < trie_cnt; i++) {
        cnt[i] = 0;
        for (int j = 0; j < M; j++) {
            trie[i][j] = 0;
        }
    }
    trie_cnt = 1;
}
 
void insert(int buffer_size, char *buf) {
    int idx = 0;
    for (int i = 0; i < buffer_size; i++) {
        int curr = buf[i] - 'a';
        if (!trie[idx][curr]) trie[idx][curr] = trie_cnt++;
        idx = trie[idx][curr];
        cnt[idx]++;
    }
}
 
int query(int buffer_size, char *buf) {
    int idx = 0;
    for (int i = 0; i < buffer_size; i++) {
        int curr = buf[i] - 'a';
        idx = trie[idx][curr];
    }
    return cnt[idx];
}