듣보잡
문제 설명
문제 설명은 사진과 같다.
알고리즘
- N,M을 입력받고 이름까지 입력 받는다
- 이분탐색을 이용하기 위해 sort 함수로 정렬한다
- 이분 탐색을 해서 중복 된 값을 찾아낸다.
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
using namespace std;
int N, M;
int main()
{
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
vector <string>v;//듣도 못한 사람
vector <string> vs;//보도 못한 사람
cin >> N >> M;
for (int i = 0; i < N; i++)//듣도 못한 사람 입력
{
string s;
cin >> s;
v.push_back(s);
}
for (int i = 0; i < M; i++)//보도 못한 사람 입력
{
string s;
cin >> s;
vs.push_back(s);
}
sort(v.begin(), v.end());//정렬
sort(vs.begin(), vs.end());
vector <string> ans;
for (int i = 0; i < N;i++)//시간을 줄이기 위한 이분 탐색 비교
{
string temp = v[i];
int left = 0;
int right = M - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (vs[mid] == temp)
{
ans.push_back(temp);
break;
}
else if (vs[mid] > temp)
right = mid - 1;
else
left = mid + 1;
}
}
cout << ans.size() << "\n";//답 갯수 출력
for (int i = 0; i < ans.size(); i++)//답 출력
cout << ans[i] << "\n";
return 0;
}
고찰
이번 문제는 단순히 문자열을 입력 받고 중복 된 값이 있는지 확인하여 그 수와 내용을 출력하면 되는 문제였다. 이분 탐색을 사용하여 간단하게 만들 수 있었다.
검색을 해보니까 직접 이진 탐색을 구현할 수 도 있고 algorithm
헤더에 있는 binary_search
함수를 사용해도 된다.
'Algorithm' 카테고리의 다른 글
[백준 1181] 단어 정렬 (0) | 2021.07.29 |
---|---|
[백준 9095] 1,2,3 더하기 (0) | 2021.07.29 |
[백준 1074] Z (0) | 2021.07.29 |
[백준 1620] 나는야 포켓몬 마스터 이다솜 (0) | 2021.07.28 |
[백준 2630] 색종이 만들기 (0) | 2021.07.28 |