코딩하기 좋은날
백준 1764 듣보잡 본문
반응형
문제와 채점은 위 사이트에서 확인 하실 수 있습니다.
이 문제는 듣과 보각각 문자열을 입력받고 둘다 해당하는 경우의 수와 문자열을 출력하는 문제입니다.
각각의 경우가 500000 까지 가능하므로 그냥 두 문자열을 비교하면 O(N^2)으로 시간 초과가 날 것입니다.
따라서 저는 multiset과 set을 이용해서 처음에 multiset에 문자열을 모두 입력받고 멀티셋의 카운트가 2인 문자열을 다시 셋에 집어넣었습니다.
코드입니다.
#include <iostream>
#include <string>
#include <set>
using namespace std;
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int N,M;
int num = 0;
cin >> N >> M;
multiset <string> ms;
string str;
set<string> s;
for(int i = 0; i < N; i++) { //multiset에 듣과 보의 입력을 받음
cin >> str;
ms.insert(str);
}
for(int i = 0; i < M; i++) {
cin >> str;
ms.insert(str);
}
for(auto it: ms) { //multiset에 2번 저장된 문자열을 set에 집어넣음
if(ms.count(it) == 2) {
s.insert(it);
num++;
}
}
cout<<num/2<<'\n'; //카운트는 2번씩 되었으니 2로 나누어줌
for(auto n: s)
cout<<n<<'\n';
return 0;
}
반응형
'백준(Baekjoon) 문제' 카테고리의 다른 글
백준 5525 IOIOI (0) | 2019.01.17 |
---|---|
백준 5598 카이사르 암호 (0) | 2019.01.16 |
백준 1032 명령 프롬프트 (0) | 2019.01.16 |
백준 2751 수 정렬하기2 (merge sort) (0) | 2019.01.15 |
백준 1427 소트인사이드 (0) | 2019.01.15 |