Python에서 모든 도시와 역 사이의 최대 거리 찾기

N개의 도시가 있고 0에서 N-1까지 번호가 매겨져 있고 역이 위치한 도시도 있다고 가정하면 모든 도시 사이의 최대 거리를 찾아야 합니다. 도시와 가장 가까운 역. 역이 있는 도시는 임의의 순서로 제공될 수 있음을 명심해야 합니다.

따라서 입력이 N =6이고 스테이션 =[2,4]인 경우 출력은 2

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

• station_present :=크기 N의 목록, False로 채우기

• 역의 각 도시에 대해

  • station_present[도시] :=참

• dist :=0, maximum_dist :=스테이션의 최소값

• 범위 0에서 N까지의 도시에 대해 수행

  • station_present[city]가 True이면

    • maximum_dist :=최대(dist + 1) / 2, maximum_dist

    • 거리 :=0

  • 그렇지 않으면

    • 거리 :=거리 + 1

• maximum_dist, dist

  의 최대값 반환

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def get_max_dist(N, station):
   station_present = [False] * N
   for city in station:
      station_present[city] = True
   dist, maximum_dist = 0, min(station)
   for city in range(N):
      if station_present[city] == True:
         maximum_dist = max((dist + 1) // 2, maximum_dist)
         dist = 0
      else:
         dist += 1
   return max(maximum_dist, dist)
N = 6
station = [2, 4]
print(get_max_dist(N, station))

입력

6, [2,4]

출력

2