2230 (1) 썸네일형 리스트형 [Baekjoon Online Judge] 2230. 수 고르기 (C++, Java) https://www.acmicpc.net/problem/2230핵심N은 최대 100,000모든 두 원소의 차를 비교하려면 시간복잡도가 O(N^2)이다. (시간초과)한 원소에 대해 조건에 맞는(차가 M 이상이면서 가장 작은) 원소를 빠르게 찾을 수 있다면, 시간복잡도를 줄일 수 있다.방법 1. 이분 탐색A[i] + M에 대한 Lower Bound는 위 조건에 맞는 원소의 인덱스와 동일하다.이를 모든 i에 대해 찾고 차를 비교하면 된다.시간복잡도는 O(NlogN)방법 2. 투 포인터 알고리즘1. 정렬 후 두 개의 포인터를 시작 지점에 둔다. (i = 0, j = 0)2. 두 원소의 차가 M보다 커지는 지점까지 j를 옮긴다.3. 차가 지금까지의 차 중에서 가장 작다면, 갱신한다.4. i를 1증가 시키고 2~.. 이전 1 다음
