[P3] 백준 19585번 전설 C++ 트라이, 해시맵, 문자열

리뷰

 

트라이와 해시맵을 사용하여 푸는 문제, 2트라이, 1트라이 1해시맵, 2해시맵 모두 풀리는 것 같다.

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

 

전역 변수

• c, n, q : 색상 정보의 개수 c, 팀 정보의 개수 n, 쿼리의 개수 q
• teams : 팀 정보를 저장할 해시맵 key : 문자열, value : 정수형으로 초기화 한다.
• Trie : 트라이를 통해 색상 정보를 저장할 구조체 소문자에 대한 정보를 트리형태로 저장한다.

 

함수

1. insert

void insert(Trie* node, const string& str)

 

1. 트라이를 통해 트리 구조에 문자를 삽입하는 함수
2. 매개변수로 Trie 타입의 현재 노드의 포인터와 입력할 문자열인 str를 받아준다.
3. 문자열을 탐색하면서 관련 노드가 존재한다면 노드를 이동한다.
4. 만약 노드가 존재하지 않는다면 new를 통해 새로 동적할당 해준다.
5. 모든 삽입이 완료되었다면 isEnd를 통해 문자열의 끝임을 명시해 준다.

 

2. query

bool query(Trie* node, const string& str)

 

1. 문자열을 입력 받고 접두사(색상)가 트라이에 존재하는지 체크하는 함수
2. 문자열을 트라이 내부에서 탐색해 주면서 관련 색상이 접두사로 존재하는지 체크해 준다.
3. 만약 isEnd가 true인 노드를 만났다면 탐색이 더 필요한 나머지 문자열이 해시맵에 존재하는지 체크해 준다.
4. 존재한다면 바로 true를 리턴해 주고 존재하지 않는다면 계속 탐색을 이어 나가준다.
5. 만약 더 이상 존재하지 않는 문자열을 만났다면 바로 false를 리턴해 주면 된다.

 

문제풀이

1. 입력을 받기 전에 먼저 root인 Trie를 동적 할당해준다.
2. c와 n값을 입력 받고, 색상 정보를 c개만큼 입력 받아 insert함수를 통해 트라이에 삽입해 준다.
3. 팀 정보를 n개만큼 입력 받아 해당 문자열이 해시맵에 존재함을 명시해 준다.
4. q를 입력 받고 q번의 쿼리를 수행하며 탐색하고자 하는 문자열을 입력 받아준다.
5. query함수를 통해 root로부터 s문자열을 탐색하고 isEnd가 true일 때마다 현재까지의 접두사를 제외한 문자열이 해시맵에 존재하는지를 체크해 준다.
6. query함수의 리턴값이 true면 Yes를 아니라면 No를 출력해 주면 된다.

 

참고 사항

처음엔 문자열 이터레이터를 통한 탐색을 진행했으나 그러면 모든 접두사에 대한 체크가 되지 않았다.

isEnd가 true인 경우에는 해시맵과 연결하여 모두 체크해 주어야 한다.

 

추천 반례

2 1
re
reds
ds
1
reds

 

 

정답 코드

#include<iostream>
#include<cstring>
#include<unordered_map>
#include<string>

using namespace std;
int c, n, q;
unordered_map<string, int> teams;

struct Trie {
	Trie* child[26];
	bool isEnd;
	Trie() {
		memset(child, 0, sizeof(child));
		isEnd = false;
	}
};

void insert(Trie* node, const string& str) {
	Trie* cur = node;
	for (const char& ch : str) {
		int idx = ch - 'a';
		if (!cur->child[idx]) cur->child[idx] = new Trie();
		cur = cur->child[idx];
	}	
	cur->isEnd = true;
}

bool query(Trie* node, const string& str) {
	Trie* cur = node;
	for (int i = 0; i < str.size(); i++) {
		int idx = str[i] - 'a';
		if (cur->isEnd && teams[string(str.begin() + i, str.end())]) return true;
		else if (!cur->child[idx]) return false;
		cur = cur->child[idx];
	}
	return false;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	Trie* root = new Trie();
	cin >> c >> n;
	for (int i = 0; i < c; i++) {
		string s; cin >> s;
		insert(root, s);
	}
	for (int i = 0; i < n; i++) {
		string s; cin >> s;
		teams[s] = 1;
	}
	cin >> q;
	while (q--) {
		string s; cin >> s;
		if (query(root, s)) cout << "Yes\n";
		else cout << "No\n";
	}
}