C++로 두 도시 간 최소 시간 간격의 최댓값 구하기

N개의 요소를 가진 배열 D가 있다고 가정해 보겠습니다. 어느 코드 페스티벌에는 Amal을 포함해 총 N+1명의 참가자가 있으며, Amal이 확인한 결과 자신의 도시와 i번째 참가자의 도시 간 현지 시간 차이는 D[i]시간이었습니다.

여기서 두 도시 간 시간 차이는 다음과 같이 정의됩니다. 24시간 표기법을 사용할 때, 도시 A의 현지 시간이 0시인 순간 도시 B의 현지 시간이 d시라면, 두 도시 간의 시간 차이는 d와 24−d 중 더 작은 값입니다.

Amal은 N+1명 중 임의의 두 사람을 선택해 만들 수 있는 모든 조합에 대해 해당 도시 간의 시간 차이를 기록했습니다. 이 값들 중 가장 작은 시간 차이를 s시간이라고 할 때, 우리가 구해야 하는 것은 s가 될 수 있는 최댓값입니다.

예를 들어 입력이 D = [7, 12, 8]이라면 출력은 4가 됩니다. 2번째 참가자와 3번째 참가자의 도시 간 시간 차이가 4시간이기 때문입니다.

해결 접근 방법

이 문제를 해결하기 위해 다음 단계를 따릅니다.

Amal의 도시를 기준점(0시)으로 삼으면, 전체 도시들은 24시간 주기를 가지는 원형 축 위의 점으로 표현할 수 있습니다.
각 참가자의 시차는 방향을 알 수 없으므로 +D[i] 또는 −D[i], 즉 24−D[i]가 될 수 있습니다.
배열 D를 오름차순으로 정렬한 뒤, 짝수 번째 인덱스에는 D[i]를, 홀수 번째 인덱스에는 24−D[i]를 교대로 배치합니다. 이렇게 하면 점들이 원 위에서 최대한 고르게 퍼지게 되어 인접한 점들 간의 최소 거리가 최대화됩니다.
마지막으로 배치된 모든 값을 다시 정렬하고, 인접한 두 값의 차이 중 최솟값을 구하면 그것이 곧 정답이 됩니다.

n := D의 크기
배열 D를 정렬
배열 t 정의
t의 끝에 0을 삽입
i := 0부터 시작하여 i < n 동안 i를 1씩 증가시키며 반복:
   i mod 2가 0이면:
      t의 끝에 D[i]를 삽입
   그렇지 않으면:
      t의 끝에 24 - D[i]를 삽입
배열 t를 정렬
ans := 무한대
i := 1부터 시작하여 i < t의 크기 동안 i를 1씩 증가시키며 반복:
   ans := ans와 t[i] - t[i - 1] 중 최솟값
ans 반환

예제 구현

아래 C++ 구현 예제를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> D) {
   int n = D.size();
   sort(D.begin(), D.end());
   vector<int> t;
   t.push_back(0);
   for (int i = 0; i < n; i++){
      if (i % 2 == 0)
         t.push_back(D[i]);
      else
         t.push_back(24 - D[i]);
   }
   sort(t.begin(), t.end());
   int ans = 1e9;
   for (int i = 1; i < t.size(); i++){
      ans = min(ans, t[i] - t[i - 1]);
   }
   return ans;
}
int main(){
   vector<int> D = { 7, 12, 8 };
   cout << solve(D) << endl;
}

입력

{ 7, 12, 8 }