글 읽기 - 시간초과의 이유를 모르겠습니다ㅠ 디버깅

yoona3316 3년 전 0

trie 이용해서 풀려고 했고요.

노드를 넣으면서 동시에 중간에 겹치는 게 있으면

( 1. 삽입 중간에 isEnd인 노드를 만나거나 2. 삽입 완료 후에 노드가 리프노드가 아닐 경우)

false 리턴하도록 했어요.

다른 질문 보니 입력을 중간에 받다 말아서 시간초과가 나는 것 같은데

제 코드는 그런 것 같지도 않습니다.

디버깅에 실패해서 고수님들께 부탁드립니다ㅠ

#include <stdio.h>
#include <string.h>
#include <iostream>
#define CHILD_SIZE 10
#define TEXT_SIZE 11

struct Node {
    bool isEnd;
    Node* child[CHILD_SIZE];

    void init() {
        isEnd = false;
        for (int i=0; i<CHILD_SIZE; i++) {
            child[i] = nullptr;
        }
    }
};
bool is_leaf(Node * curr);

Node* trie;

void init() {
    trie = new Node;
    trie->init();
}

int to_int(char c) {
    return c-'0';
}
bool add_node(const char* words) {
    Node* curr = trie;
    for (; *words; words++) {
        if (curr->isEnd) return false;
        int idx = to_int(*words);
        if (curr->child[idx]==nullptr) {
            curr->child[idx] = new Node;
            curr->child[idx]->init();
        }
        curr = curr->child[idx];
    }
    curr->isEnd = true;
    return is_leaf(curr);
}

bool is_leaf(Node * curr) {
    for (int i=0; i<CHILD_SIZE; i++) {
        if (curr->child[i]!=nullptr) return false;
    }
    return true;
}

int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase>0) {
        init();
        int n;
        scanf("%d", &n);
        getchar();
        bool is_consistant = true;
        while (n>0) {
            char* words = (char*)malloc(sizeof(char)*TEXT_SIZE);
            fgets(words, TEXT_SIZE, stdin);
            words[strlen(words)-1] = '\0';
            if (is_consistant) {
                is_consistant &= add_node(words);
            }
            n--;
        }
        if (is_consistant) printf("YES\n");
        else printf("NO\n");
        testcase--;
    }
}

yoona3316 3년 전 0

fgets()로 입력받았더니 엄청 느린가보네요ㅠ

scanf로 바꿨더니 잘 됩니당!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과의 이유를 모르겠습니다ㅠ 디버깅

yoona3316 3년 전 0

yoona3316 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말