N개의 도시가 있으며, 각 도시는 0부터 N-1까지 번호가 매겨져 있다고 가정해 보겠습니다. 또한 역이 설치된 도시들의 목록도 함께 주어집니다. 우리가 구해야 하는 값은 임의의 도시에서 가장 가까운 역까지의 거리 중 최대값입니다. 이때 역이 있는 도시들은 순서에 상관없이 주어질 수 있다는 점에 유의해야 합니다.
예를 들어 입력이 N = 6이고 stations = [2, 4]라면 출력은 2가 됩니다. 도시 0에서 가장 가까운 역(2번)까지의 거리가 2로, 모든 도시 중 가장 먼 거리이기 때문입니다.
문제 해결 접근 방법
이 문제는 선형 탐색 한 번으로 해결할 수 있습니다. 알고리즘의 핵심 아이디어는 다음과 같습니다.
- 첫 번째 역 이전의 도시들은 첫 역까지의 거리가 곧 최대 후보가 되므로, 초기 maximum_dist는 station의 최솟값으로 설정합니다.
- 역과 역 사이에 연속된 dist개의 역 없는 도시가 있을 때, 그 구간에서 가장 가까운 역까지의 거리는 양쪽 끝 역 기준 (dist + 1) // 2가 됩니다.
- 마지막 역 이후 남은 dist 값도 최종 결과와 비교하여 더 큰 값을 반환합니다.
구체적인 해결 단계는 다음과 같습니다.
- station_present := 크기가 N인 리스트를 생성하고 False로 채웁니다.
- station의 각 도시에 대해 station_present[city] := True로 설정합니다.
- dist := 0, maximum_dist := station의 최솟값으로 초기화합니다.
- 0부터 N-1까지 각 도시를 순회하며 다음을 수행합니다.
- station_present[city]가 True이면 maximum_dist := max((dist + 1) // 2, maximum_dist)로 갱신하고, dist := 0으로 초기화합니다.
- 그렇지 않으면 dist := dist + 1을 수행합니다.
- 최종적으로 maximum_dist와 dist 중 더 큰 값을 반환합니다.
Python 구현 예제
더 나은 이해를 위해 다음 구현 코드를 살펴보겠습니다.
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
동작 과정 살펴보기
위 예제에서 도시 0~5가 있고 역은 2번과 4번에 위치합니다. 도시 0은 2번 역까지 거리가 2이고, 도시 1은 거리 1, 도시 3은 양쪽 역 모두 거리 1, 도시 5는 4번 역까지 거리 1입니다. 따라서 전체 최대 거리는 2가 됩니다.
이 알고리즘은 도시 배열을 한 번만 순회하므로 시간 복잡도는 O(N), 역 유무를 저장하는 리스트 때문에 공간 복잡도 역시 O(N)입니다. 역이 많거나 도시 수가 많은 경우에도 효율적으로 동작합니다.