1. 80%에서 틀리시는 분은 아래 반례를 한번 확인해보세요

1

1 1 -1 -1 

2. 이분탐색으로 시간초과 나시는 분 참고하세요

n는 4천이기 때문에, 중간에서 만나기로 샘플을 만들게 되면 O(N^2)이 되어 32,000,000이 됩니다.

N^2에 대해서 Lower, Upper Bound 탐색 시 각각 LogN의 시간이 걸리기 때문에 2logN이 걸립니다. 값들을 곱해보면 대략 12~13억번의 탐색이 필요합니다.

문제에서 주어진 테스트 타임은 12초입니다. 따라서, 굉장히 간당간당하게 통과할 수 밖에 없습니다. 

이분탐색으로 접근하신 분들께서는 짜신 코드가 O(N^2*logN)을 만족하시는지 확인하시고, 만족하는데 TLE가 난다면 최적화 문제일 수 있으니

함수 호출, 혹은 최적화 관점에서 계속 확인해보시면 될 것 같습니다. 

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