[코딩테스트 연습] 숫자 게임

 

문제: https://programmers.co.kr/learn/courses/30/lessons/12987

---

원소 B[i]가 이길 수 있는 A[i]의 원소 중 max(A[i])를 계속 매칭해주면 됩니다.

 

배열 B의 각 원소에 대한 탐색은 최소 N만큼 이뤄져야 하고,

N제한이 10만이므로 O(N^2)이 해가 되면 터집니다.

 

그러므로 각 원소에 대한 탐색은 logN만에 탐색을 해야 NlogN으로 시간초과를 피할 수 있을 것입니다.

 

그래서 logN 탐색 방법 중 이분탐색으로 해결하였습니다.

 

A, B 배열 모두를 오름차순으로 정렬한 뒤, B배열의 맨 뒤에서부터

B[i]가 이길 수 있는 A 배열의 숫자 중 가장 큰 수랑 매칭하도록 해줍니다.

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/summer_winter03.cc