문제 풀이/백준 알고리즘

[baekjoon 14425] 문자열 집합- 문자열, map (C++)

dev_beomgeun 2020. 12. 24. 19:08
728x90

www.acmicpc.net/problem/14425

 

14425번: 문자열 집합

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.  다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어

www.acmicpc.net

요즘 map 자료구조를 연습 중이다.

이 문제는 간단한 문제인데 map 자료구조를 사용해서 해당 string key 값을 통해 value값을 비교해서 풀어주었다.

 

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

using namespace std;

int N, M, cnt;
string word;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	unordered_map<string, bool> m;
	for (int i = 0; i < N; i++) {
		cin >> word;
		m[word] = true;
	}
	for (int i = 0; i < M; i++) {
		cin >> word;
		if (m[word])
			cnt++;
	}
	cout << cnt;
}

key는 string, value는 bool로 두고 찾아야 하는 N개의 단어를 true로 바꿔준다.

그 이후에 이 N개의 단어들이 해당되는지 비교할 M개의 단어 집합을 입력받으면서 이 단어들을 key로 만약 그 단어가 true이면 세준다.

 

이 문자열 문제는 map을 이용할 수도 있고, 트라이라는 자료구조를 이용해서 풀 수도 있다.

트라이 자료구조를 통해 다른 문제를 풀어봐야겠다.

728x90