글 읽기 - 틀렸습니다가 어디서 나오는지 모르겠습니다.

martinok1103 3년 전 0

isEnd는 종료하는 단어인지 확인

isDelete는 삭제하는 단어인지 확인

isNonDel은 삭제하지 않는 단어인지 확인

delLeft는 내 트라이 이하에서 삭제할 단어가 몇개 남았는지

nonDelLeft는 내 트라이 이하에서 삭제하지 않을 단어가 몇개 남았는지

cnt는 내 트라이에서 몇 개의 가지가 뻗어져 나갔는지

를 나타냅니다.

rm *을 사용하는 경우는 이미 if문으로 전처리 해놓았습니다.

어느 부분에서 틀렸는지 확인해주시면 감사하겠습니다.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char getIdx(char key) {
    if(key >= 'a' && key <= 'z') return key-'a';
    else if(key >= 'A' && key <= 'Z') return key-'A'+(char)26;
    else if(key >= '0' && key <= '9') return key-'0'+(char)52;
    else if(key == '.') return (char)62;
}

char getChar(char num) {
    if(num >= 0 && num <= 25) return num+'a';
    else if(num >= 26 && num <= 51) return num+'A'-26;
    else if(num >= 52 && num <= 61) return num+'0'-52;
    else if(num == 62) return '.';
}

struct Trie {
    bool isEnd;
    bool isDelete;
    bool isNonDel;
    int delLeft;
    int nonDelLeft;
    int cnt;
    Trie* next[63]; //0~25 large 26~51 small 52~61 num 62 dot

    Trie(): isEnd(false), isDelete(false), isNonDel(false), cnt(0), nonDelLeft(0), delLeft(0) {
        for(int i=0 ; i<63 ; i++) {
            next[i] = NULL;
        }
    }

    ~Trie() {
        for(int i=0 ; i<63 ; i++) {
            if(next[i]) delete next[i];
        }
    }

    void insert(const char* key) {
        if(*key == 0) {
            isEnd = true;
            isNonDel = true;
            nonDelLeft = 0;
            return;
        }
        char inp = getIdx(*key);
        if(next[inp] == 0) {
            cnt++;
            next[inp] = new Trie();
        }
        nonDelLeft++;
        next[inp]->insert(key+1);
    }

    void insertDel(const char* key) {
        if(*key == 0) {
            isEnd = true;
            isDelete = true;
            delLeft = 0;
            return;
        }
        char inp = getIdx(*key);
        if(next[inp] == 0) {
            cnt++;
            next[inp] = new Trie();
        }
        delLeft++;
        next[inp]->insertDel(key+1);
        //printf("{%s %d}\n",key,delLeft);
    }

    int delCnt() {
        if(nonDelLeft == 0) return cnt;
        int sum = 0;
        if(isDelete && nonDelLeft > 1) sum++;
        for(int i=0 ; i<63 ; i++) {
            if(next[i]) {
                int t = next[i]->delCnt();
                //printf("[%c %d]\n",getChar(i),t);
                sum += t;
            }
        }
        return sum;
    }
};

void sol() {
    char era[1001][22];
    char ner[1001][22];

    int n1, n2;
    scanf("%d",&n1);
    for(int i=0 ; i<n1 ; i++) {
        scanf(" %s",&era[i]);
    }
    scanf("%d",&n2);
    for(int i=0 ; i<n2 ; i++) {
        scanf(" %s",&ner[i]);
    }
    if(n2 == 0) {
        printf("1");
        return;
    }
    Trie* root = new Trie();
    for(int i=0 ; i<n1 ; i++) {
        root->insertDel(era[i]);
    }
    for(int i=0 ; i<n2 ; i++) {
        root->insert(ner[i]);
    }
    printf("%d\n",root->delCnt());
    delete root;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--) {
        sol();
    }
}

ghssh1 3년 전 0

일단은 Trie cnt가 초기화가 안되어있네요

martinok1103 3년 전 0

초기화 구문 추가했는데도 틀렸다고 뜨네요

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

문제

문제

출처

ICPC

틀렸습니다가 어디서 나오는지 모르겠습니다.

martinok1103 3년 전 0

ghssh1 3년 전 0

martinok1103 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말