이분탐색을 재귀적으로 구현하셨는데 여기서
Binary_search_count(data[:mid], x)
해당 코드에서 data[:mid] 의 시간복잡도는 data라는 배열에서 K개만큼 잘라서 새로운 배열을 생성하는 것이니 O(K)입니다.
그러면 총 시간복잡도는 (arr의 크기만큼 도는 50만 * (공비가 1/2인 초깃값 25만의 합) => 50만)
즉, 50만 * 50만이므로 시간초과가 나올겁니다.
새로운 배열을 생성하는 대신 기존 배열에서 index를 가지고 이분탐색을 하게끔 수정해보시면 될 것 같네요.
kwonjoosung 1년 전
이진 탐색을 통해 리스트를 쪼개고 난 후에 count함수를 사용했는데도 시간 초과가 나옵니다.
이 문제 이진 탐색으로 해결이 가능한 건가요...