4158

속도를 어떻게 높일 것인가에 대한 문제인데

문제에서 힌트로 주어지는 CD 넘버가 오름차순을 띤다고 했다.

가장 일반적으로 생각할 수 있는 방법은 트리 구조임을 이용해 O(nlogn)시간 내에 푸는 방법이 있을 수 있지만

상근이와 선영이의 CD로 주어지는 넘버 모두 오름차순을 띈다는 점을 이용해

O(N)시간에 해결 할 수 있다.

#include<iostream> #include<cstdio> using namespace std; int a[1000000], b[1000000]; int main() { int piv_a, piv_b; int size_a, size_b; int cnt; while(true){ scanf("%d %d", &size_a, &size_b); if(size_a == 0 && size_b == 0) break; cnt=0; for(int i = 0; i < size_a; i++) scanf("%d", &a[i]); for(int j = 0; j < size_b; j++) scanf("%d", &b[j]); for(piv_a=0, piv_b=0; piv_a < size_a && piv_b < size_b; ) { if(a[piv_a] == b[piv_b]){ cnt++; piv_a++; piv_b++; } else if(a[piv_a] < b[piv_b]) piv_a++; else piv_b++; } printf("%d\n", cnt); } return 0; }