woaksths   2년 전

이분탐색을 재귀로 돌려서 풀었습니다.

30%에서 계속 시간초과가 나는데, 혹시 더 최적화할 수 있는 방법이 있는지, 혹은 다른 알고리즘 접근 방법으로 풀어야하는지 여쭙고 싶습니다.


감사합니다.

pmn0001   2년 전

수의 범위가 -10000000~10000000 이라 입력을 배열에 담는 방법도 있습니다

계차정렬할때 사용하는 방법으로요

palilo   2년 전

n개의 카드가 모두 x라고 합시다

binary_search(0, len(arrs)-1, x)는 n을 리턴해야 합니다.

즉, (line 9)에서 count += 1가 n번 실행돼야 합니다. 복잡도가 O(n)이겠네요

카드에서 x의 가장 왼쪽 위치를 이분 탐색으로 찾고, 마찬가지로 가장 오른쪽 위치도 이분 탐색으로 찾고,

그 사이의 거리를 구해주면 O(log n) + O(log n) + O(1)으로 쿼리를 처리할 수 있겠네요

woaksths   2년 전

이해했습니다. 

target x를 찾기보다, target x가 연속적으로 나올 경우 시간복잡도가 O(n)이 걸리니 

가장 왼쪽에 나오는 target x의 position_left와 가장 오른쪽에 나오는 target x의 position_right를 구해서

position_right - position_left를  구하라는 의미이군요.

감사합니다. 

댓글을 작성하려면 로그인해야 합니다.