[Codeground][74] 버스타기

문제 : https://www.codeground.org/practice/practiceProblemViewNew

---

5 3
1 4 3 7 9

을 예로 들어보자.

일단 오름차순으로 정렬한다.
1 3 4 7 9
첫번째 수 1과 같은 버스를 탈 수 없는 바둑 기사와 같이 탈 수 있는 바둑기사를 나눠보면 다음과 같다.
1 3 4 7 9
차이가 작은 수들이 같은 버스를 탈 수 없다.

따라서 1과 같은 버스를 탈 수 없는 바둑 기사들은 각자 누구와도 같은 버스를 탈 수 없다. (정렬했기 때문에 빨간색 범위 내의 능력차이는 항상 3(4-1)보다 작다.)

즉, 1 3 4는 각자 다른 버스를 타야하고 따라서 적어도 3개의 버스가 필요하다. 나머지 7과 9는 1번이 탄 버스에 같이 타면 되므로 같이 탈 수 없는 바둑 기사의 수만 고려하면 된다.

각 바둑 기사들과 같이 탈 수 없는 바둑 기사들의 수를 구한 뒤 이 중 가장 큰 값이 정답이 된다.

투포인트를 사용하면 정렬하는데 NlogN이 들고 배열을 2N만큼 탐색하므로 시간복잡도는 O(NlogN).

---

소스코드 : https://gist.github.com/fpdjsns/fd7ad20bc1fb0b6d05568b4c5997d9c7