[백준 알고리즘] 1764번: 듣보잡
May 05, 2020
448. Find All Numbers Disappeared in an Array
문제
김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.
출력
듣보잡의 수와 그 명단을 사전순으로 출력한다.접근 방법:
처음에는 벡터를 두개 사용해서 find함수를 통해 해결하려고 했는데, std::find 함수는 모든 배열 요소를 검사하는 O(N^2) 의 복잡도를 가진다. 그래서 시간초과를 해결하기 위해 set을 사용하기로 했다. set 자료구조는 아이템이 들어갈 때마다 자동으로 정렬이 되고 이미 정렬된 배열이기 때문에 find함수도 이진탐색을 기반으로 한 O(log n) 의 복잡도를 가진다.
통과 코드:
#include <iostream>
#include <set>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
set<string> dnames;
set<string> bnames;
set<string> result;
int N, M;
cin >> N >> M;
int t = N+M;
while(t--){
string name;
cin >> name;
if(t >= M) dnames.insert(name); // 듣도 못한 이름들 넣기
else bnames.insert(name); // 보도 못한 이름들 넣기
}
// 셋은 넣을 때 자동으로 소팅이 되기 때문에 셋에 사용되는 find는 바이너리 서치(O(log n))를 사용한다. 일반 std::find 는 모든 원소를 다 검사하기 떄문에 O(n^2).
for (set<string> :: iterator dit = dnames.begin() ; dit != dnames.end() ; dit++){
if(bnames.find(*dit) != bnames.end()) result.insert(*dit); // 듣고 못한 이름중에 보도 못한 이름에 이름이 있는지 확인하고 결과셋에 넣기
}
// 결과 출력 //
cout << result.size() << "\n";
for (string r : result){
cout << r << "\n";
}
return 0;
}
