kwonjoosung   1년 전

이진 탐색을 통해 리스트를 쪼개고 난 후에 count함수를 사용했는데도 시간 초과가 나옵니다. 

이 문제 이진 탐색으로 해결이 가능한 건가요...

jeonggu223   1년 전

이분탐색을 재귀적으로 구현하셨는데 여기서

Binary_search_count(data[:mid], x)

해당 코드에서 data[:mid] 의 시간복잡도는 data라는 배열에서 K개만큼 잘라서 새로운 배열을 생성하는 것이니 O(K)입니다.

그러면 총 시간복잡도는 (arr의 크기만큼 도는 50만 * (공비가 1/2인 초깃값 25만의 합) => 50만)

즉, 50만 * 50만이므로 시간초과가 나올겁니다.

새로운 배열을 생성하는 대신 기존 배열에서 index를 가지고 이분탐색을 하게끔 수정해보시면 될 것 같네요.

kwonjoosung   1년 전

감사합니다! 

하지만 코드를 바꿔보아도 시간 초과는 여전하네요.. 

jeonggu223   1년 전

9번째 return하는 쪽을 생각해봅시다!

만약 상근이가 10 카드를 50만개 갖고 있고, 구해야 할 카드들의 목록이 모두 10이라고 가정해보면

첫 번째 재귀 -> 8번째 라인에 걸릴 것이고 data[start : end+1]로 새로운 배열을 생성했으니 50만이라는 시간복잡도

count(x)의 시간복잡도는 해당 배열 길이만큼 순회하며 x와 같은 값을 찾는 것인데 이에 대한 시간복잡도도 50만이겠죠?

총 시간복잡도를 계산해보면 28번째 라인 for문에서 50만번 * (새로운 배열 생성 (50만) + count함수 (50만)) 으로 결국 시간초과가 날 겁니다.


그렇다면 모든 수를 흝어봐야 하는 것이니 for문을 도는 건 어쩔 수 없을 겁니다. 새로운 배열 생성 + count 함수되는 부분을 줄여보면 되겠죠?

해당 숫자를 찾을 때마다 count를 하기보다는 미리 상근이가 갖고 있는 숫자들을 count를 해둔 뒤, 만약 값을 찾았다면 O(1)로 바로 해당 값이 몇 개 있는지 알 수 있는 방법으로 생각해보면 좋을 것 같습니다!

kwonjoosung   1년 전

Counter를 통해서 해결했습니다! 감사합니다!!

공부 열심히 해야겠군요.. 친절한 답변 감사드립니다!


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