[BOJ] 백준 1764 듣보잡

[BOJ] 백준 1764 듣보잡

문제 링크 : https://www.acmicpc.net/problem/1764


이 문제는 일견 쉬워보이지만 테스트케이스 N,M이 각각 50만개여서 시간초과 오류가 나기 쉽습니다. 저도 시간초과 오류에 많이 빠졌습니다. 제가 푼 방법 순서대로 4가지는
1. 듣도못한 사람들, 보도못한 사람들 각각 벡터로 받고 각각 sort 후 일치하면 출력.
2. 듣도못한 사람들, 보도못한 사람들 각각 벡터로 받고 일치하는것들 모아서 sort후 출력.
3. a-z 까지 26개 벡터 생성 후 각각 초성에 따라 분류해서 sort.
하였으나, 모두 시간초과 오류가 났습니다.


2중 for문을 사용할때, 50만X50만 시간이 소요돼서 그렇습니다.
만약, for문을 한개씩만 사용한다면 50만 * (for문의 개수) 시간이 소요 될 것입니다.
따라서 한꺼번에 듣도못한 사람, 보도못한 사람 모두 받고, 이 벡터를 sort한 후 중복되는 것들만 출력 한다면 50만 * 3 의 시간이 소요됩니다.




소스코드 :

#include 
#include 
#include 
#include 
using namespace std;

int main() {
 int ta, tb;
 cin >> ta >> tb; cin.ignore();
 vector res;
 vector v(ta+tb);

 // 벡터 v에 듣,보 한꺼번에 받는다.
 for (int i = 0; i < ta + tb; i++) {
  cin >> v[i]; cin.ignore();
 }

 // 전체 sort 실시.
 sort(v.begin(), v.end());

 // 중복되는 이름은 res 벡터에 push.
 for (int i = 0; i < ta + tb; i++) {
  if (v[i] == v[i + 1]) {
   res.push_back(v[i]);
   i += 1;
  }
 }
 int rsize = res.size();
 cout << rsize << endl;
 for (int i = 0; i < rsize; i++) {
  cout << res[i] << '\n';
 }

}