14425 문자열 집합[c++] unordered_set

 

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

14425번: 문자열 집합

문제 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.  다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다. 입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지...

www.acmicpc.net

 

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    unordered_set<string> words1;
    for (int i = 0; i < n; ++i) {
        string temp;
        cin >> temp;
        words1.insert(temp);
    }

    int count = 0;
    for (int i = 0; i < m; ++i) {
        string temp;
        cin >> temp;
        if (words1.find(temp) != words1.end())
            count++;
    }

    cout << count;
    return 0;
}

 

 

밑에 코드는 처음에 작성했던 초안이다. 정답은 나오지만 시간이 초과되었었다.

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;


inline bool check(string a, string b) {  //check 함수
	int checkidx = 0;
	if (a.length() == b.length()) {
		for (int i = 0; i < a.length(); i++) {
			if (a[i] == b[i]) {
				checkidx++;
			}
			else return 0;
		}
		if (checkidx == a.length()) {
			return 1;
		}
	}
	else return 0;
	
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	vector<string> words1;


	for (int i = 0; i < n; i++) {
		string temp;
		cin >> temp;
		words1.push_back(temp);
	}
	int count = 0;
	for (int i = 0; i < m; i++) {
		string temp;
		cin >> temp; 
		for (int j = 0; j < n; j++) {
			if (check(temp, words1[j])){
				count++;
				break;
			}
		}
	}
	cout << count;
	return 0;
}

 

우선 vector을 사용했기 때문에 비교하는 함수를 따로 만들어줘야 했다. 또한 check라는 함수에서 다 맞으면 true를 return하는 시간이 오래걸리는 함수로 짰다. 틀리면 바로 false로 바꿔주면 더 시간이 줄어든다.

unordered set을 사용한다면 따로 check 함수를 사용하지 않고 find를 사용하면 되고 시간복잡도도 O(1)로 줄일 수 있다.

---

Unordered_Set

 

주요 특징

1. 빠른 검색: 해시 함수를 사용하기 때문에 검색이 빠르다.
2. 중복을 허용하지 않음 : 각 원소가 유일하며 중복된 원소 허용 x
3. 순서 없음 : 원소들이 삽입된 순서를 기억하지 않는다.

이러한 특징들로 인해 unordered_set는 원소의 삽입과 검색이 빈번하게 발생하는 상황에서 매우 유용하다.

 

주요 멤버 함수

• insert(val) : 주어진 값 val을 삽입
• erase(val) : 주어진 값을 제거
• find(val) : 주어진 값(val)을 가진 원소를 검색하여 해당 원소의 반복자(iterator)를 반환, 만약 원소를 찾지 못하면 unordered_set의 끝을 나타내는 end iterator를 반환
• size(): unordered_set에 저장된 원소의 개수 반환
• empty() : unordered_set이 비어있는지 여부를 반환