문제링크
https://www.acmicpc.net/problem/14426
풀이방법
해당 문제를 트라이 알고리즘을 공부하기 위한 목적으로 트라이 알고리즘을 이용하여 풀었다. 트라이 알고리즘이란 문자열을 효율적으로 처리하기 위한 트리 자료 구조이다.
check함수를 이용하여 검사해야 하는 문자열의 문자를 앞쪽부터 탐색한다. 특정 문자에서 존재하지 않는 부분이 발견된다면 false를 반환하고 끝까지 탐색했는데 존재하지 않는 부분이 발견되지 않는다면 true를 반환해서 최종적으로 입력된 특정 문자열의 접두사로 판단하여 ans의 개수를 1 증가 시킨다.
트라이 알고리즘에 대해서 잘 몰라서 공부가 필요하면 아래 영상을 참고하자 문제에 대한 상세 풀이도 존재한다.
코드
#include <bits/stdc++.h>
using namespace std;
const int MX = 10000*500 + 5;
const int ROOT = 1;
int unused = ROOT + 1;
int nxt[MX][26];
int n, m;
int ctoi(char c){
return c - 'a';
}
void insert(string& s){
int cur = ROOT;
for(char c : s){
if(nxt[cur][ctoi(c)] == -1)
nxt[cur][ctoi(c)] = unused++;
cur = nxt[cur][ctoi(c)];
}
}
bool check(string& s){
int cur = ROOT;
for(char c : s){
if(nxt[cur][ctoi(c)] == -1)
return 0;
cur = nxt[cur][ctoi(c)];
}
return 1;
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < MX; i++)
fill(nxt[i], nxt[i] + 26, -1);
string s;
while(n--){
cin >> s;
insert(s);
}
int ans = 0;
while(m--){
cin >> s;
ans += check(s);
}
cout << ans;
}
'CS(Computer Science)지식 > [C++][코딩 테스트] 자료구조 및 알고리즘' 카테고리의 다른 글
[C++] 백준 5052번: 전화번호 목록 (0) | 2024.02.04 |
---|---|
[C++] 백준 14425번: 문자열 집함 (0) | 2024.02.03 |
[C++] 백준 1786번: 찾기 (0) | 2024.02.03 |
백준 14938번: 서강그라운드 (C++) (0) | 2024.02.03 |
백준 1504번: 특정한 최단 경로 (C++) (0) | 2024.02.03 |