[C++]백준 - 1764번 문제

1764번: 듣보잡 (acmicpc.net)

1764번: 듣보잡

 

1764번 : 듣보잡

---

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

 

 

출력

---

듣보잡의 수와 그 명단을 사전순으로 출력한다.

 

 

---

 

생각해 볼 점

---

어떤 자료구조를 써도 괜찮고, 어떻게 풀어도 괜찮은 문제입니다.

 

set, hash, vector, array 아무거나 써서 문제에서 요구하는 대로 구현합니다.

 

메모리도 시간 제한도 넉넉하기 때문에, 쉽게 풀 수 있습니다.

 

정렬의 경우는 STL을 활용해서 편하게 사용하거나, 그냥 set만으로 문제를 풀어버릴 수도 있습니다.

 

set은 중복 제거 및 자동 정렬을 수행해주므로, set을 활용한 풀이를 선호합니다.

 

코드

---

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

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

	int N, M;
	cin >> N >> M;
	set<string> names;

	//듣도 못한사람 명단
	while (N--)
	{
		string input;
		cin >> input;

		names.insert(input);
	}

	vector<string> ans;
	int ans_num = 0;
    //보도 못한 사람 명단 입력
	while (M--)
	{
		string input;
		cin >> input;
		
        //듣도 못한 사람 명단에 존재하지 않으면 추가
		if (names.find(input) != names.end())
		{
			ans_num++;
			ans.push_back(input);
		}
	}
    //사전 순 정렬
	sort(ans.begin(), ans.end());

	cout << ans_num << "\n";
	for (string name : ans)
	{
		cout << name << "\n";
	}

	return 0;
}

 

그 외

---