ppmyor   1년 전

처음에 find로 풀었는데 메모리 초과가 나서 투포인터 방법으로 바꾸었더니 시간초과가 납니다.

줄일 수 있는 부분은 다 줄였다고 생각이 드는데 혹시 시간을 더 줄일 수 있는 부분이 있을까요?

게시판에 js가 별로 없어 이렇게 질문 드립니다.

oyhoyhk   1년 전

투 포인터에서 right 값 시작이

소수를 담고 있는 arr 배열 끝에서 시작할 때

arr의 길이가 엄청 길 때 (target의 max가 100000000 이라면 arr의 길이는 65500개가 넘어갑니다)

target = 20 이라고 하면 right 값을 찾기 위해 6만번이 넘는 right-- 연산을 해줘야 합니다

따라서 right 값을 -1 씩 빼서 찾는 것이 아니라 이진탐색으로 찾아 준다면 시간 초과를 해결 할 수 있습니다






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