[5446번] 용량 부족

문제 출처 :

https://www.acmicpc.net/problem/5446

알고리즘 분석 :

문제 해결에 필요한 사항

1. 트라이

트라이를 쓸 줄 알면 풀 수 있는 문제이다.

우선 첫번째로 들어오는 지워야할 파일을 모두 트라이에 담아준다.

그 후 두번째로 지우면 안되는 파일을 트라이에 보내면서 지나가는 단어마다 isForbidden = true로 설정해준다.

(이때 지워야할 파일명이 이미 트라이에 있는데 지우지 말아야할 파일명이 트라이 안에 없다면 break를 해준다.

예를들어 filenames은 지워야할 파일인데 files로 시작하 파일은 지우면 안되는 파일이지만 트라이에 없으므로 

file까지만 isForbidden = true을 해주고 break를 해주면 된다.)

이제 트라이를 모두 구성했으니 queue에 트라이 현재 위치 포인터를 담아 트라이를 조사해보자.

isForbidden = true이면 다음 단어를 queue에 넣으며 넘어가야 한다.

이때 단어의 끝까지 조사가 됐다면 그 단어는 지워야 한다.(forbidden이어도 지워야할 단어이므로)

즉, ans++

만약 현재 위치가 isForbidden = false이면 이 단어뒤로부터는 *을 통해 모두 지울 수 있으므로

ans++만하고 queue에는 집어넣지 않는다.

이때 예외는 m == 0이라면 *로 모든 파일을 지우면 되니 답은 1이다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149

#include <iostream> #include <cstdio> #include <queue>   using namespace std;   const int MAX_NODE = 63;   int convert(char ch) {     if ('a' <= ch && ch <= 'z')         return (ch - 'a');     else if ('A' <= ch && ch <= 'Z')         return (37 + ch - 'A');       else if (ch == '.')         return 26;       else if ('0' <= ch && ch <= '9')         return (ch - '0' + 27); }   char recover(int n) {     if (0 <= n && n <= 25)         return ('a' + n);     else if (n == 26)         return '.';     else if (27 <= n && n <= 36)         return (n - 27 + '0');     else if (37 <= n && n <= 63 - 1)         return (n - 37 + 'A'); }     struct Trie {     Trie *next[MAX_NODE];     bool isEnd, isForbidden, hasChild;     Trie() {         for (int i = 0; i < MAX_NODE; i++)         {             next[i] = nullptr;             isEnd = isForbidden = false;         }     }       ~Trie() {         for (int i = 0; i < MAX_NODE; i++)             if (next[i])                 delete next[i];     } };   Trie *root;   int main() {     int tc;     scanf("%d", &tc);       while (tc--)     {         root = new Trie;           int n;         scanf("%d", &n);           for (int i = 0; i < n; i++)         {             char str[25];             scanf("%s", str);               Trie *pos = root;             for (int j = 0; str[j]; j++)             {                 int nowCh = convert(str[j]);                   if (!pos->next[nowCh])                     pos->next[nowCh] = new Trie;                   pos = pos->next[nowCh];             }               pos->isEnd = true;         }           int m;         scanf("%d", &m);           if (!m)         {             printf("1\n");             continue;         }         for (int i = 0; i < m; i++)         {             char str[25];             scanf("%s", str);               Trie *pos = root;               for (int j = 0; str[j]; j++)             {                 int nowCh = convert(str[j]);                   if (pos->next[nowCh])                     pos->next[nowCh]->isForbidden = true;                 else                     break;                   pos = pos->next[nowCh];             }         }           int ans = 0;         queue<Trie *> q;           q.push(root);           while (!q.empty())         {             Trie *cur = q.front();               q.pop();             for (int i = 0; i < MAX_NODE; i++)             {                 if (cur->next[i])                 {                     if (cur->next[i]->isForbidden)                     {                         if (cur->next[i]->isEnd)                             ans++;                           q.push(cur->next[i]);                     }                     else                         ans++;                 }             }         }           printf("%d\n", ans);     }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus