[Silver IV] 듣보잡 - 1764

문제 링크

성능 요약

메모리: 20676 KB, 시간: 52 ms

분류

자료 구조, 해시를 사용한 집합과 맵, 정렬, 문자열

제출 일자

2024년 8월 19일 16:46:39

문제 설명

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

입력

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

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

출력

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

제출코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.txt", "r", stdin);
	 
	int N, M;
	cin >> N;
	cin >> M;
	
	string* ptrN = new string[N];
	string* ptrM = new string[M];
	vector<string> vec;

	for (int i = 0; i < N; i++)
	{
		cin >> ptrN[i];
	}
	for (int i = 0; i < M; i++)
	{
		cin >> ptrM[i];
	}

	unordered_set<string> setN(ptrN, ptrN + N);
	unordered_set<string> setM(ptrM, ptrM + M);

	for (const auto& m : setM) {
		if (setN.find(m) != setN.end()) {
			vec.push_back(m);
		}
	}

	sort(vec.begin(), vec.end());
	cout << vec.size() << "\n";

	for (int i = 0; i < vec.size(); i++)
	{
		cout << vec[i] << "\n";
	}

	return 0;
}

풀이

두 명단의 중복을 찾는 간단한 문제인데, N,M의 범위가 커 전체 탐색으로는 불가능하다.

해시를 사용한 map을 사용했고, 그 중에 원소의 순서가 상관없어, 탐색 평균 O(1) 최악O(n)인 unordered_map을 이용했다.

한 집단씩 set을 만들어주고 다른 set에 한 원소씩 탐색해 결과 vec에 담아 출력하였다.

다른 풀이 방법

• 첫번째 문제에서는 N,M 집단으로 나누어 설명하지만 N,M 각각의 집단에서 중복이 없다고 밝혀져있다. 따라서 사실상, N,M 구분없이 모든 문자열을 그대로 다 받고 N+M, 그안에서 중복된 문자열만 뽑도록 구현하여도 무방해 보인다.

for (int i = 0; i < N+M; i++) {
        string str;
        cin >> str;
        MAP[str]++;
        if (MAP[str] > 1) // 중복되면
            VECTOR.push_back(str);
    }

• 두번째 찾아본 두번째 방법으로는 binary_search를 사용한 방법이다. 사용하기전에 탐색할 자료형이 sort된 상태여야 한다. 시간 복잡도가 O(log N)으로 성능이 빠른 편이다.

...
for (int i = 0; i < M; i++){
	
	if (binary_search(setN.begin(),setN.end(),setM[i]))
}
for (const auto& m : setM) {
		if (binary_search(setN.begin(),setN.end(),m)) {
			vec.push_back(m);
		}
	}