선택한 위치의 최소 간격

수직선의 위치가 적힌 항목 중 k개를 골라요. 선택한 항목을 위치 순서로 나열했을 때, 서로 이웃한 선택 항목 사이 거리의 최솟값을 가능한 한 크게 만들어요.

int solution(vector<int> positions, int k)를 작성해 그 최소 간격의 최댓값을 반환해 주세요. 배열 길이는 212, k는 2N이고 위치는 0~1,000인 정수예요. 순서는 임의이고 같은 위치가 여러 번 나올 수 있어요. 같은 위치의 항목도 별개지만 둘을 고르면 간격이 0이에요. 최적 선택이 여러 개면 간격만 반환해요. 빈 배열은 없고 반환형은 int예요.

예시 1: positions = {1, 2, 4, 8, 9}, k = 3 → 3. 1·4·8을 고르면 간격 3·4의 최솟값은 3이에요. 간격 4 이상으로 세 개를 고를 수는 없어요.

예시 2: positions = {0, 5, 10, 15}, k = 3 → 5. 0·5·10 또는 0·10·15 등에서 최소 간격 5를 얻어요.

실행 입력은 N k, 다음 줄의 위치 N개예요. 아래 하네스가 매개변수를 구성하므로 solution만 작성해요.

5 3
1 2 4 8 9

3

4 3
0 5 10 15

5