[백준 / C++] 1764번: 듣보잡 (정렬 문제)

https://www.acmicpc.net/problem/1764

1764번: 듣보잡

 

일단 듣도 못한 사람 (hear)과 보도 못한 사람 (see)를 입력받고 각각 정렬시킨다

그 후 merge sort에서 merge할 때처럼 정렬된 두 개의 배열에 커서를 두고 각각의 커서가 가리키는 같으면 배열 ans에 넣어주었다.

커서가 가리키는 이름 서로 다를 때는 사전순으로 더 앞선 쪽의 커서를 1칸 이동시킨다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, i, j;
	cin >> n >> m;

	vector<string> hear;
	vector<string> see;
	string name;
	for (i = 0; i < n; i++) {
		cin >> name;
		hear.push_back(name);
	}
	for (i = 0; i < m; i++) {
		cin >> name;
		see.push_back(name);
	}

	sort(hear.begin(), hear.end());
	sort(see.begin(), see.end());

	i = 0; j = 0;
	vector<string> ans;
	while (i < n && j < m) {
		int cmp = hear[i].compare(see[j]);
		if (!cmp) {
			ans.push_back(hear[i]);
			i++;
			j++;
		}
		else if (cmp > 0)
			j++;
		else
			i++;
	}
	int size = ans.size();
	cout << size << "\n";
	for (i = 0; i < size; i++)
		cout << ans[i] << "\n";
}

 

코드 제출 결과