구하고자 하는 것은 상근이가 카드를 가지고 있는지의 유무이다.
이분탐색 카테고리에 있어서 이분탐색으로 풀려했으나 아이디어가 떠오르지 않았다.
오히려 완탐만 떠올랐다...
완탐방법은 다음과 같다.
-천만 ~ 천만으로 이천만개 숫자만 저장하면 된다.
N이 50만밖에 안되니까 50만번만 반복해서 상근이가 가지고 있는 카드를 저장한다.
M이 50만이니까 50만번 반복해서 특정 숫자가 상근이가 가지고 있는 숫자인지 배열에서 확인하면 된다.
이분탐색으로는 어떻게 풀지?
두 배열을 정렬해서 포인터를 두고 비교하나...?그러면 나중에 출력은 정렬 이전의 순서대로 출력해야되는데 이 부분은 어떻게 하는가..?
상근이가 가지고 있는 카드를 정렬한다.
상근이가 찾는 숫자가 갖고있는지 이분탐색을 통해서 그냥 탐색하면 된다. logN이라서 가능하다.
m번 이분탐색 하면 되는거였다.
