ehdwns2045   1년 전

용액문제에서.. 시간초과가 뜹니다..!ㅠㅠ

이래저래 고쳐서 테스트하였더니 78%까지 체점되다가 그 이후에 시간초과가 뜨네요.


오름차순으로 숫자가 입력되는 것을 감안해,

오른쪽 숫자부터 비교하도록 하였고 두 수의 합이 더 작아지지 않는다면 break 로 다음 수를 비교하도록 하였습니다.

그리고 0이 가장 최소값이므로 0이면 바로 정답을 출력하도록 했고..

양쪽 숫자의 합이므로, 이미 방문한 숫자는 빼도록 하였습니다.


시간을 더 줄일 수 있는 방법이 무엇이 있을까요..?

조언 부탁드립니다.^^

exqt   1년 전

하나를 정하고 이진 검색으로 지금 break 걸리는 부분을 O(logN)에 찾을 수 있습니다.

안쪽 for문을 이진 검색으로 대체하면 O(NlogN) 에 해결 되겠네요.

ehdwns2045   1년 전

아! 그렇군요ㅎㅎ
감사합니다.

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