C++로 도시와 가장 가까운 역 사이의 최대 거리 찾기

개념

도시의 개수 N(0번부터 N-1번까지 번호가 매겨짐)과 역이 설치된 도시들의 목록이 주어졌을 때, 각 도시에서 가장 가까운 역까지의 거리 중 최댓값을 구하는 것이 이 문제의 목표입니다. 역이 있는 도시들은 특정한 순서 없이 임의로 주어질 수 있다는 점에 유의해야 합니다.

입력 및 출력 예시

예시 1:

numOfCities = 6, stations = [2, 4]

출력:

2

예시 2:

numOfCities = 6, stations = [4]

출력:

4

예시 설명

첫 번째 예시에는 총 6개의 도시가 있으며, 역이 설치된 도시는 아래 그림에서 초록색으로 표시되어 있습니다. 이 경우 가장 가까운 역에서 가장 멀리 떨어진 도시는 0번 도시이며, 그 거리는 2입니다. 따라서 최대 거리는 2가 됩니다.

두 번째 예시에서는 역이 4번 도시 하나에만 존재합니다. 가장 가까운 역에서 가장 멀리 떨어진 도시는 0번 도시이며, 그 거리는 4입니다. 따라서 최대 거리는 4가 됩니다.

접근 방법

이 문제는 가장 먼 도시의 위치에 따라 다음 세 가지 경우로 나누어 생각할 수 있습니다.

• 첫 번째 경우: 가장 먼 도시가 두 역 사이에 위치한 경우
• 두 번째 경우: 가장 먼 도시가 첫 번째 역의 왼쪽에 위치한 경우
• 세 번째 경우: 가장 먼 도시가 마지막 역의 오른쪽에 위치한 경우

알고리즘 단계

1. 도시 수 N과 같은 크기의 불리언 배열을 false로 초기화한 뒤, 역이 있는 도시의 값을 true로 표시합니다.
2. 현재 거리를 저장할 변수 dist를 0으로 초기화하고, 최대 거리를 저장할 변수 maxDist는 첫 번째 역이 있는 도시의 번호로 초기화합니다(두 번째 경우를 처리하기 위함).
3. 모든 도시를 처음부터 끝까지 하나씩 순회합니다.
4. 현재 도시에 역이 있다면, maxDist를 (dist + 1) / 2와 기존 maxDist 중 더 큰 값으로 갱신하고 dist를 0으로 되돌립니다(첫 번째 경우 처리).
5. 역이 없다면 dist를 1씩 증가시킵니다.
6. 순회가 끝나면 dist와 maxDist 중 더 큰 값을 반환합니다(세 번째 경우 처리).

이 알고리즘은 모든 도시를 한 번만 순회하므로 시간 복잡도는 O(N), 역 보유 여부를 저장하는 배열 때문에 공간 복잡도 역시 O(N)입니다.

C++ 구현 예제

// C++ 프로그램: 임의의 도시와
// 가장 가까운 역 사이의 최대 거리 계산
#include<bits/stdc++.h>
using namespace std;
// 각 도시에서 가장 가까운 역까지의
// 거리 중 최댓값을 계산하는 함수
int findMaxDistance(int numOfCities, int station[], int N){
   // 역 보유 여부를 나타내는 불리언 배열 초기화
   bool hasStation[numOfCities + 1] = {false};
   // 역이 있는 도시를 true로 표시
   for (int i = 0; i < N; i++){
      hasStation[station[i]] = true;
   }
   int dist = 0;
   int maxDist = INT_MAX;
   // 첫 번째 역의 위치로 maxDist 초기화 (왼쪽 끝 경우 처리)
   for(int i = 0; i < N; i++){
      maxDist = min(station[i], maxDist);
   }
   // 모든 도시를 순회하며 최대 거리 계산
   for (int city = 0; city < numOfCities; city++){
      if (hasStation[city] == true){
         // 두 역 사이에 있는 경우 처리
         maxDist = max((dist + 1) / 2, maxDist);
         dist = 0;
   }
   else
      dist += 1;
   }
   // 마지막 역 오른쪽 끝 경우 처리
   return max(maxDist, dist);
}
// 드라이버 코드
int main(){
   int numOfCities = 6;
   int station[] = {2,4};
   int N = sizeof(station)/sizeof(station[0]);
   cout << "Max Distance:" << findMaxDistance(numOfCities,
   station, N);
}

실행 결과

Max Distance:2