1764번 - 듣보잡 | 시간초과, binary search (C++)

 

---

문제

---

풀이

  1. 처음에는 이중 for문을 이용해 풀이했다. 당연히 시간초과 발생 O(n²)

      ➡ 애초에 최댓값이 50만씩이여서, 50만 x 50만 = 시간 초과가 날 수 밖에 없었음..

 

  2. 시간초과 문제를 해결하기 위해서는, map 또는 binary search를 사용해야 한다.

      ➡  map: O(logn), Red-Black Tree, key - valued의 pair로 저장된다. 중복 허용 X

      ➡  binary search: O(logn), 꼭 정렬을 먼저 해줘야 한다.

 

나는 binary search를 이용해 문제를 해결했다.

 

추가로, vector는 데이터 순차 저장이므로 검색 속도가 느리다.

검색에는 hash_map(unordered_map)과 map을 사용하는 것이 빠르다.

hash_map(unordered_map)은 정렬을 하지 않기 때문에, 시간복잡도가 O(1)이다.

map은 자동으로 정렬하며, 시간복잡도가 O(logn)이다.

---

 첫 번째 풀이 _ 시간초과 발생 | 이중 for문, O(n²)

// 시간초과 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m;
	string hearname, seename;
	vector<string> hearv, seev, answerv;

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> hearname;
		hearv.push_back(hearname);
	}

	for (int i = 0; i < m; i++) {
		cin >> seename;
		seev.push_back(seename);
	}
	
	sort(hearv.begin(), hearv.end());
	sort(seev.begin(), seev.end());


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (hearv[i] == seev[j]) {
				answerv.push_back(hearv[i]);
			}
		}
	}

	cout << answerv.size() << "\n";
	
	for (auto a : answerv) {
		cout << a << "\n";
	}
	
	return 0;
}

 

 

---

 두 번째 코드 | binary search, O(logn)

// binary_search 사용 | O(logn)
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	string hearname, seename;
	vector<string> hearv, answerv;
	int n, m;

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> hearname;
		hearv.push_back(hearname);
	}

	sort(hearv.begin(), hearv.end());

	for (int i = 0; i < m; i++) {
		cin >> seename;
		if (binary_search(hearv.begin(), hearv.end(), seename)) {
			answerv.push_back(seename);
		}
	}
	
	sort(answerv.begin(), answerv.end());

	cout << answerv.size() << "\n";

	for (auto a : answerv) {
		cout << a << "\n";
	}

	return 0;
}

---

결과

 

 

 

1764번: 듣보잡