백준 1764 - 듣보잡

문제링크

• 백준 1764

문제 접근

• 순차탐색(sequential search)은 가장 간단하고 직접적인 탐색 방법이지만 데이터양이 많아질수록 비효율적이다. 이번 문제에서도 순차탐색의 경우 시간초과에 걸린다.
• 정렬된 배열에서 탐색할 수 있다면 이진탐색(binary search)이 가장 효과적이다. 이진탐색은 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다. 이렇게 매 단계에서 검색해야 할 리스트의 범위를 반으로 줄인다.

의사코드(pseudo-code)

# define function
bool cmp(const string& str1, const string& str2)
	- return str1 < str2

# main
- cin >> n >> m
- vector<string> no_hear(n)
- len = n<m ? n : m
- idx = 0
- vector<string> result(len)
- for i=0 to n-1:
	- cin >> no_hear[i]
- sort(no_hear.begin(), no_hear.end(), cmp)
- for i=0 to m-1:
	- cin >> str
	- if binary_search(no_hear.begin(), no_hear.end(), str) is true:
		- result[idx++] = str
- sort(result.begin(), result.begin()+idx, cmp)
- cout << idx
- for i=0 to idx-1:
	- cout << result[i]

소스코드 및 분석

전체 코드

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

bool cmp(const std::string& str1, const std::string& str2) {
	return str1 < str2;
}

int main()
{
	int n, m;
	std::cin >> n >> m;
	std::vector<std::string> no_hear(n);
	int len = n < m ? n : m;
	int idx = 0;
	std::vector<std::string> result(len);
	for (int i = 0; i < n; i++)
		std::cin >> no_hear[i];
	std::sort(no_hear.begin(), no_hear.end(), cmp);
	for (int i = 0; i < m; i++) {
		std::string str;
		std::cin >> str;
		if (std::binary_search(no_hear.begin(), no_hear.end(), str))
			result[idx++] = str;
	}
	std::sort(result.begin(), result.begin() + idx, cmp);
	printf("%d\n", idx);
	for (int i = 0; i < idx; i++)
		std::cout << result[i] << "\n";
}

• algorithm 헤더파일에 있는 binary_search 함수를 이용했다. 이진탐색을 진행하기 전에 배열은 반드시 “정렬”되어 있어야함에 주의하자.
• 벡터컨테이너를 선언할 때 size 를 미리 설정해두어 일반 배열처럼 데이터를 삽입, 삭제 할 수 있도록 했다. 따라서, 경우에 따라 메모리를 확장해야하는 과정이 불필요하여 시간을 아낄 수 있다.

다른 풀이

• 시간복잡도를 O(n)으로 줄여야 제한 시간 안에 통과할 수 있을 것이라 생각했다. (sort 함수를 호출했으니 O(nlogn)) 정도의 시간 복잡도 일 것이다.
• 듣도 못한 사람 중에서는 중복된 이름이 없고, 보도 못한 사람 중에서도 중복된 이름이 없으니 두 부류에 모두 속한 사람만이 전체 명단에서 2번 존재하게 된다.
• 전체명단을 입력 받아 오름차순 정렬한 뒤 같은 이름이 연속으로 나열된 사람이 듣도 보도 못한 사람이 된다.

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

bool cmp(const string& s1, const string& s2) {
	return s1 < s2;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	int total = n + m;
	vector<string> all_people;
	for (int line = 0; line < total; line++) {
		string str;
		cin >> str;
		all_people.push_back(str);
	}
	sort(all_people.begin(), all_people.end(), cmp);

	vector<string> ans;
	for (int i = 0; i < total - 1; i++) {
		if (all_people[i] == all_people[i + 1])
			ans.push_back(all_people[i++]);
	}
	cout << ans.size() << endl;
	for (auto ele : ans)
		cout << ele << endl;
}