우주 정거장 최대 거리 구하기

얼마 전에 알고리즘 문제 하나 풀었습니다.

 

각 도시에서 가장 가까운 우주 정거장까지의 거리가 가장 먼 경우를 찾는 문제입니다.

 

문제 원문입니다.

 

============================================================================

 

서울랜드는 여러 도시와 우주 정거장을 가지고 있는 나라입니다. 도시들은 연속된 번호가 부여되어있고 각각 다음 도시까지 연결된 도로의 길이는 1Km입니다.입니다 순환 가능한 도로가 아니므로, 첫 번째 도시와 마지막 도시와 연결되지 않습니다. 어떤 도시에서 가장 가까운 우주 정거장까지의 거리가 먼 경우를 찾아내야 합니다.

 

n = 3 인 도시가 있고 우주 정거장이 도시 1번에 있다고 합시다. 도시 2는 2 - 1 = 1 단위만큼 떨어져 있고, 도시 3 은 3 - 1 = 2 단위만큼, 도시 1 은 우주 정거장에서 가장 가까운 곳으로 0 단위만큼 떨어져 있습니다. 그중에 가장 먼 거리는 2입니다.입니다.

 

n: 전체 도시의 수

m: 우주 정거장이 있는 도시 개수

c: 우주 정거장이 있는 도시의 index 가 있는 정수 배열. 1부터 시작하는 인덱스

 

입력 형식

첫 번째 라인은 공백으로 구분되어 있는 두 정수 n과과 m으로으로 구성되어 있습니다.

두 번째 라인은 우주 정거장을 가지고 있는 각각의 도시의 인덱스를 포함하는 공백으로 구분되어 있는 m 개의 정수가 있다. 이 값들은 유일한 값으로 구성되어 있고 정렬되어 있지 않습니다.

 

제약사항

1 <= n <= 10^5

1 <= m <= n

우주 정거장은 반드시 1개 이상이 도시에 존재합니다.

하나 이상의 우주 정거장을 가진 도시는 없습니다.

 

출력 형식

서울랜드의 우주 비행사가 가장 가까운 우주 정거장에 도착하기 위해 필요한 최대 거리를 정수로 출력합니다.

 

문제 예제 화면

 

============================================================================

 

소스 코드

 

제가 작성한 소스 코드를 보게 되시면

 

전체 도시의 개수와 우주 정거장 인덱스가 있는 배열을 각각 정수 a와 정수 배열 c로 입력받아서 진행하고 있습니다.

 

그리고 각 도시의 가장 가까운 우주정거장의 최대 거리를 구합니다. (17~36라인)

 

마지막으로 각 도시에서 가장 가까운 우주정거장까지의 거리가 가장 먼 거리를 구합니다. (38~42라인)

 

전체적인 소스를 리뷰해보면 17~36라인을 개선할 필요가 있는 것 같습니다.

 

굳이 모든 우주 정거장 인덱스 배열을 다 순회하지 않고

 

각 도시별 앞, 뒤에 있는 우주 정거장 거리만 확인하면 더 효율적일 거 같습니다.

 

단 우주 정거장 위치 인덱스가 오름차순으로 입력한 경우에 한해서입니다.

(예시: 3 5 8 14 ...)

 

그렇지 않고 임의의 순서대로 입력한다면 전제 조회해야 합니다.

(예시: 6 1 10 5 ...)