BJ_2230 썸네일형 리스트형 [Two-Pointer] BJ_2230, 수 고르기 [문제의 접근] 두 수를 선택하고, 두수의 차이가 M이상이면서 가장 작은 차이를 구해야 한다. 어떻게 접근해야 할까? Bruteforce로 접근하면 가장 쉽게 접근법을 생각할 수 있다. 즉 모든 경우의 수를 비교해 보는 것이다. N개의 수 중에서 2개의 수를 임의로 선택해야 하기 때문에, $O(N^2)$ 시간 복잡도가 나온다. For 문을 계층적으로 2번 돌린다고 생각하면 쉽다. 첫번째 수를 정하고 N-1개 비교, 2번째 수를 정하고 N-2개 비교,.... 현재 N이 1,000이하라면 충분하겠지만, 주어진 값은 N이 100,000 으로 주어져 있다. 연산량은 $10^{10}$으로 대략적인 1초의 연산량 $10^8$을 초과하므로 시간초과다. 그럼 어떻게? $O(n\log_{2}{n})$의 접근이나, $O(.. 더보기 이전 1 다음
