[백준 BOJ] 1764 듣보잡 C++

백준 1764번: 듣보잡

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

1764번: 듣보잡

---

문제

예제

• 문제 해석 및 풀이

  듣도 못한 사람의 수 N과 보도 못한 사람의 수 M을 차례로 입력을 받고 그 아래로 각각 N명의 사람의 명단과 M명의 사람의 명단을 입력을 받는다. 그리고 두 명단에서 중복되는 사람의 수를 출력하고 이어서 중복되는 사람들의 이름을 사전순으로 출력한다.

  일단 입력을 받기 위해서 두 개의 벡터가 필요하고 중복되는 사람의 수를 카운트하기 위해 cnt변수를 만들었다. 그리고 두번째 명단을 받을 때, find함수로 첫번째 명단에 있는 사람들만 받게 만들고 이와 동시에 cnt를 +1씩 올리면 문제가 거의 해결된다. 이제 두번째 명단을 정렬한 뒤에 출력한 하면 된다.

---

초안(시간초과)

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

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
	int n, m;
	string str;
	int cnt = 0;
	vector<string> heard, seen;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> str;
		heard.push_back(str);
	}
	for (int i = 0; i < m; i++) {
		cin >> str;
		if (find(heard.begin(), heard.end(), str) != heard.end()) {
			cnt++;
			seen.push_back(str);
		}
	}
	sort(seen.begin(), seen.end());
	cout << cnt << "\n";
	for (int i = 0; i < seen.size(); i++) {
		cout << seen[i] << "\n";
	}
	return 0;
}

예제까지 정답이었지만 백준에 제출해보니 결과는 시간초과..

---

• 문제해결

 시간초과의 원인을 찾아야 한다. 코드를 분석해보니 유력한 원인은 중복을 찾을 때 쓰는 find 함수였다. find 함수의 시간복잡도는 O(N) 이다. 하지만 반복문 안에 find 함수가 위치해 있으니 시간복잡도는 O(N²)이 되고 여기서 문제가 발생했을 것이다. find 대신 활용할 수 있는 것은 이진탐색이다. 이진탐색의 시간복잡도는 O(logN)이고 이를 활용하면 총 시간복잡도는 O(NlogN)이 될 것이다. 이진탐색을 사용하기 위해서는 벡터를 미리 정렬시켜줘야 한다.

 

• 최종코드
  

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

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);
	int n, m;
	string str;
	int cnt = 0;
	vector<string> heard, hseen;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> str;
		heard.push_back(str);
	}
	sort(heard.begin(), heard.end());
	for (int i = 0; i < m; i++) {
		cin >> str;
		if (binary_search(heard.begin(), heard.end(), str)) {
			cnt++;
			hseen.push_back(str);
		}
	}
	sort(hseen.begin(), hseen.end());
	cout << cnt << "\n";
	for (int i = 0; i < hseen.size(); i++) {
		cout << hseen[i] << "\n";
	}
	return 0;
}

binary_search()를 사용하기 위해서는 배열(벡터)을 정렬한 상태로 사용해야 한다. 따라서 sort로 heard를 정렬해준 후 hseen의 입력을 받았다. 

 

 

• 정리

 전체적으로 '집합과 맵' 단계에 있는 다른 문제와 비슷해서 어려운 문제는 아니라고 생각한다. find() 대신 이진탐색을 쓰는 것이 정렬을 해줘야 하는 번거로움이 있지만 시간에서 이득을 볼 수 있다. 반면 정렬을 유지하기 번거롭고 큰 데이터를 다루지 않는다면 선형 탐색인 find()를 사용하는 것이 더 나을 것이다.

 궁금한 것이나 더 나은 코드 및 방법, 그리고 잘못된 것이 있다면 댓글에 남겨주시기 바란다.