BOJ 1764 듣보잡

문자열 처리하는 문제이다.

처음엔 시간초과 났는데, 단순하게 이중 for문으로 '듣도못한'에 해당하는 문자열과 입력받은 문자열을 비교하여 벡터에 저장하고, 그 벡터를 소팅하여 출력했다 (...)

 

하지만...이 문제는 매우 간단하다

일단 이 문제는 2개 (듣도못한 / 보도못한)의 겹침 밖에 존재하지 않는다는 것이 핵심이다. 즉 한 문자열이 나올 수 있는 최대의 경우는 두번이다.

즉, 받은 모든 문자열을 소팅하면 당연히 중복된 문자열 두개는 문자열 내에서 바로 이웃해있게 된다.

이를 이용해서 풀면된다.

 

1) n+m 만큼 문자열 입력을 받는다

2)벡터를 소팅한다.

3)소팅한 벡터에서 v1.at(i-1) == v1.at(i) 라면 v2에 해당 문자열을 넣어준다.

 

#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;

int main(void) {
	vector<string>v1;
	vector<string>v2;
	int n, m;
	cin >> n; //듣도
	cin >> m;  //보도
	int nm=0; //듣보잡
	string tmp;
	for (int i = 0; i < n + m; i++) {
		cin >> tmp;
		v1.push_back(tmp);
	}
	sort(v1.begin(), v1.end());
	for (int i = 1; i < n + m; i++) {
		if (v1.at(i) == v1.at(i - 1)) 
		{  v2.push_back(v1.at(i)); }
	}
	cout << v2.size() << endl;
	for (int i = 0; i < v2.size(); i++)
		cout << v2.at(i) << endl;

}