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

1. 문제이해

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

1764번: 듣보잡

 

듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때,

듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하는 것이 목표이다.

 

 

 

2. 문제풀이

 

듣도 못한 N명의 명단과 보도 못한 M명의 명단이 주어질 때,

듣도 보도 못한 사람들의 명단을 구하는 프로그램이다.

이해하기 쉽게 말하자면, 두 집합의 교집합을 구하는 문제이다.

 

N명의 사람들의 명단을 입력받은 후, M명의 사람들을 입력받음과 동시에

앞선 N명의 사람들 중 해당 사람이 있는지 확인해주면 된다.

단, N, M은 500,000 이하의 자연수이기 때문에,

무작정 for문을 이용해 하나씩 확인한다던지 vector의 find 함수를 이용해 확인하게 되면 시간초과가 발생한다.

따라서 다른 자료구조를 이용해야 하는데 필자는 이진탐색을 이용했다.

 

이진 탐색에 대한 자세한 내용은 아래 포스팅의 문제와 함께 설명되어있으니

참고 바랍니다.😊

https://beginnerdeveloper-lit.tistory.com/15

[C] 백준 1920번 수 찾기

 

 

 

3. 소스코드

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

int main() {
	int N, M;
	string input;
	vector <string> v;
	vector <string> result;
	int cnt = 0;

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> input;
		v.push_back(input);
	}

	// 이진 탐색 적용 전 정렬 필수
	sort(v.begin(), v.end());
	for (int i = 0; i < M; i++) {
		cin >> input;
		// 이진 탐색
		if (binary_search(v.begin(), v.end(), input)) {
			cnt++;
			result.push_back(input);
		}
	}

	cout << cnt << "\n";
	sort(result.begin(), result.end());
	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << "\n";
	}

	return 0;
}

2. 문제풀이에 따른 소스코드는 위와 같다.

N명의 듣도 못한 사람들을 입력받아 벡터 v에 저장 후, 이를 정렬한다.

(이진 탐색 이전에 정렬은 필수이다.)

 

정렬된 벡터 v를 이용해 M명의 보도 못한 사람들을 입력받으며,

만약 듣도 보도 못한 사람이라면, 즉, 두 집합에 모두 속하는 사람이라면

듣도보도 못한 사람의 수를 세어주고(cnt++) result 벡터에 값을 넣어준다.

(필자는 따로 binary tree(이진 탐색 트리)를 구현하지 않고 algorithm 내의 내장함수를 이용했다.

내장 함수가 있는 줄 알았다면 진작 썼을텐데..^^ 여지껏 하나하나 구현했었다니..)

 

모든 M명의 사람들에 대한 탐색이 끝나면, cnt 값을 출력하고,

result에 있는 듣도보도 못한 사람들의 명단을 정렬 후 출력한다.

 

 

---

일주일 뒤면 벌써 개강이라니...😭😭😭

이제 개강한 대학생이 되어 돌아오겠습니다...😈