24라인에서 right를 다시 left+1로 초기화를 하고 있는데. 예를 들어, 30라인 까지 돌아서 left=3, right=1000일 때, 다시 for문으로 돌아가게 되면, right가 1000에서 left+1 인 4로 초기화 됩니다. 30라인을 통해서 (3, 1000)일 때, 간격이 처음으로 M보다 작기(또는 가깝기) 때문에 right=1000까지는 탐색 할 필요가 없음에도 불구하고 right가 4인 시점에서 다시 시작하게 됩니다. 이렇게 불필요한 탐색을 여러 번 하는 과정에서 상당한 시간이 소요되는 것으로 보입니다.
그리고 이 코드는 통과됨에도 불구하고 반례가 존재합니다. 1, 11이 처음으로 간격이 6이상 인 것을 확인 한 후, 32라인의 v[right]-v[left]<M 조건문으로 인하여 4,11이 7로 가까운 간격임에도 불구하고 left가 4를 지나치고 끝까지 이동합니다.
qkralsdk39 2년 전
안녕하세요 2230 문제를 풀고 궁금증이 생겨 질문글을 올립니다.
저는 이 문제를 풀면서 for문을 돌며 두 포인터의 위치가 가르키는 값이 M보다 커질때 까지 포인터를 이동시키는
while(v[right]-v[left]<M && right<N) right++ 이런 방식으로 문제를 접근했는데요
이후 다른 풀이를 보다보니
while (1) { if (v[right] - v[i] >= M) { ans = min(ans, v[right] - v[i]); break; } else if (right == N - 1) break; right++; }이런식으로 푸는게 훨씬 시간이 적게 나오는걸 확인했습니다. ㅜㅜ
같은 풀이에서 위 부분만 바꿔도 시간이 엄청 차이났는데요 (800ms, 20ms)
두개 조건문을 확인해서 만족할때까지 변수를 증가시킨다는건 같은 방식인거 같은데
왜이렇게 시간차이가 많이나는건지 궁금합니다