1764 풀이
※ 문제 링크 : https://www.acmicpc.net/problem/1764
이 문제는 개인적으로 재밌는 문제라서 가져왔습니다. 먼저 문제에서 들어보지 못한 사람 N명에 대한 리스트와 그 다음에 보지도 못한 사람 M명에 대한 리스트를 제공을 합니다. 그리고 이 서로 다른 리스트에서 중첩되는 이름을 찾아 듣도 보도 못한 사람을 찾는 게 이 문제의 핵심입니다.
이 문제는 먼저 각 리스트를 벡터로 입력을 받아서 저장을 한 후에 각각의 리스트를 이름 순서대로 정렬을 하도록 합니다.
정렬이 완료되면 아래와 같은 방식으로 탐색을 실시하도록 합니다.
A C E F U V ↑ ↓ B D E U
A C E F U V x ↑ ↓ B D E U
A C E F U V x ↑ x ↓ B D E U
A C E F U V x x ↑ x ↓ `B D E U
A C E F U V x x ↑(MATCH) x x ↓(MATCH) B D E U
A C E F U V x x x ↑ x x x ↓ B D E U
A C E F U V x x x x ↑(MATCH) x x x ↓(MATCH) B D E U
A C E F U V x x x x x ↑ x x x x ↓(HALT) B D E U
이에 따라, 만들어지는 코드는 아래와 같습니다.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int N, M;
vector<string> cannot_hear;
vector<string> cannot_see;
void init(){
cin >> N >> M;
for(int _case = 0; _case < 2; _case++) {
int how_many = _case == 0 ? N : M;
for (int i = 0; i < how_many; i++) {
string name;
cin >> name;
if(_case == 0)
cannot_hear.push_back(name);
else
cannot_see.push_back(name);
}
}
}
void run(){
vector<string> cannot_head_and_see;
sort(cannot_see.begin(), cannot_see.end());
sort(cannot_hear.begin(), cannot_hear.end());
vector<string>::iterator search_see = cannot_see.begin();
vector<string>::iterator search_hear = cannot_hear.begin();
while(true){
if(*search_see == *search_hear) {
cannot_head_and_see.push_back(*search_see);
*search_see++; *search_hear++;
}
else if(*search_see > *search_hear)
search_hear++;
else
search_see++;
if(search_see == cannot_see.end() ||
search_hear == cannot_hear.end() )
break;
}
cout << cannot_head_and_see.size() << endl;
for(auto i : cannot_head_and_see) cout << i << endl;
}
int main(){
init();
run();
}