donghy9508   2년 전

i와 j값을 고정시켜두고 그 mid를 이진탐색하는 알고리즘으로 짜서 시간복잡도는 O(N^2logN)입니다.

그래서 시간초과는 나지 않을것 같은데

i와 j값이 달라야하고 mid는 i,j와 달라야하기 때문에 이진탐색의 조건을 left+2<=right로 하였습ㄴ다.

그래서 시간초과는 나지 않는데 제출해보면 틀렸다고 나옵니다. 그래서 정올에 제출해보니까

15개 테스트케이중에서 7개 테스트 케이스는 통과하는데 나머지 8개 테스트 케이스를 통과를 못합니다,

이진탐색을 구현할때 그 절대값이 작은 쪽으로 가게 해야 될거같은데

제 조잡한 실력으로는 여기까지입니다,ㅠㅠ

도움 부탁드립니다.

chogahui05   2년 전

의도대로 푸시려면

arr[i] + arr[j] = k라고 할 때

[i+1, j-1] 구간에서 -k와 제일 가까운 수를 뽑아야 하는 것 아닌가요? 그런데 이건.. upper_bound나 lower_bound 정도로 쉽게 해결 가능하고요.


중간 처리를 잘못 하셔서 틀렸습니다가 뜬 거 같아요.

보통 ~와 가까운 수를 찾아라. 이러는 경우는

이웃한 항들도 같이 검사하는 경우가 있거든요.


그리고 O(n^2logn)으로는 5000*5000*13=3억 얼마..

시간초과가 날 거 같네요.

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