1- // Authored by : BaaaaaaaaaaarkingDog
1+ // Authored by : scsc3204
22// Co-authored by : -
3- // http://boj.kr/****************
3+ // http://boj.kr/2ac3becd640f49c0813660ad18387058
44#include < bits/stdc++.h>
55using namespace std ;
66
7- int main (void ){
7+ const int MX = 20 * 1000 * 2 + 2 ;
8+ const int ROOT = 1 ;
9+
10+ int n, unused;
11+ vector<pair<char , int >> trie[MX]; // trie[cur] = {char, nxt}
12+ bool is_wc_app[MX]; // is wild card applicable
13+ bool chk[MX]; // should be removed
14+
15+ int find (char c, int cur) {
16+ for (auto [d, nxt] : trie[cur])
17+ if (c == d) return nxt;
18+ return -1 ;
19+ }
20+
21+ void insert (string &s, bool code) {
22+ int cur = ROOT;
23+ is_wc_app[ROOT] = code;
24+ for (char c : s) {
25+ int nxt = find (c, cur);
26+ if (nxt == -1 ) {
27+ nxt = unused;
28+ trie[cur].push_back ({c, unused++});
29+ }
30+ is_wc_app[nxt] = code;
31+ cur = nxt;
32+ }
33+ chk[cur] = code;
34+ }
35+
36+ int search (int cur) {
37+ if (is_wc_app[cur]) return 1 ;
38+
39+ int res = chk[cur];
40+ for (auto [c, nxt] : trie[cur])
41+ res += search (nxt);
42+ return res;
43+ }
44+
45+ void solve () {
46+ fill (is_wc_app, is_wc_app + MX, 0 );
47+ fill (chk, chk + MX, 0 );
48+ unused = 2 ;
49+
50+ for (int i = ROOT; i < MX; i++)
51+ trie[i].clear ();
52+
53+ cin >> n;
54+ for (int i = 0 ; i < n; i++) {
55+ string s; cin >> s;
56+ insert (s, 1 );
57+ }
58+ cin >> n;
59+ for (int i = 0 ; i < n; i++) {
60+ string s; cin >> s;
61+ insert (s, 0 );
62+ }
63+ int ans = search (ROOT);
64+ cout << ans << ' \n '
65+ }
66+
67+ int main () {
868 ios::sync_with_stdio (0 );
969 cin.tie (0 );
10-
11- }
70+
71+ int t; cin >> t;
72+ while (t--) solve ();
73+ }
74+ /*
75+ 초기 세팅
76+ - N1과 N2가 각각 최대 1000개씩일 수 있으며,
77+ 파일 이름은 20글자 이하기 때문에
78+ MX값을 20 * 1000 * 2 + 2로 설정했습니다.
79+
80+ 영문 대소문자가 총 52개이므로
81+ 확인해야 하는 문자가 많아 2차원 배열로 다음 노드를 구현할 경우
82+ 시간이 꽤 걸릴 수 있을 거라 판단하여,
83+ 트라이 노드는 페어의 동적 배열 형태로 구현하였습니다.
84+
85+
86+ insert 함수 동작
87+ - 지워야 하는 파일의 이름들을 삽입할 때는
88+ 와일드카드를 붙일 수 있다고 표시합니다.
89+ 이는 cur까지 오면서 만든 문자열 뒤에
90+ *을 붙여 rm 명령을 할 수 있다는 의미로 구현했습니다.
91+
92+ 예를 들어, 예제에 나온 것 같이 clean이 지워야 하는 문자라면
93+ (ROOT) -> c -> l -> e -> a -> n을 거치면서 is_wc_app 값을 1로 설정하는데,
94+ 이는 '*', 'c*', 'cl*', 'cle*', 'clea*', 'clean*' 명령을 쓸 수 있는 상태임을 의미합니다.
95+
96+ 이후 삽입이 끝난 후 마지막 노드에는 chk 값을 설정합니다(33번째 줄).
97+
98+ 지우면 안 되는 파일의 이름들을 삽입할 때는
99+ 와일드카드를 적용할 수 없다고 표시합니다(30번째 줄).
100+
101+
102+ search 함수로 연산 수 계산
103+ - search 함수로 인접한 트라이 노드를 확인하며
104+ 필요한 rm 연산 수를 계산합니다.
105+ 특별히 와일드카드를 적용할 수는 없지만
106+ 지워야 하는 파일의 이름은 chk로 표시되어 있기 때문에
107+ 현 노드에서 지워야 하는 연산 수에 이를 추가합니다(39번째 줄).
108+
109+ 만약 현노드에 와일드카드를 적용할 수 있는 경우,
110+ 한 번의 연산이 필요하므로 1을 반환합니다.
111+ */
0 commit comments