문제 설명

서울시에 일직선 모양의 새로운 도로가 생겼습니다. 새로운 도로의 전체 길이는 l이고 도로에는 총 n개의 가로등이 세워졌습니다. 이 도로의 모든 가로등에 전구를 사서 달려고 합니다. 전구를 선택하는 기준은 다음과 같습니다.

• 1) 전구는 길의 좌측, 우측 방향으로 각각 d 길이만큼 길을 밝힐 수 있고, d는 자연수입니다.
• 2) 모든 가로등에는 같은 종류(d 값이 같은)의 전구를 달아야 합니다.
• 3) 안전을 위하여 도로위에 어두운 부분이 있어서는 안 됩니다.

이때, d 값이 충분히 크다면 전체 도로를 밝게 비출 수 있지만, d 값이 작아진다면 도로 위에 빛이 닿지 않는 부분이 생길 수도 있습니다. 따라서, 도로 위에 어두운 부분이 생기지 않도록 하는 d 값 중 최솟값을 구하려고 합니다. 전체 도로의 길이 l, 가로등이 세워져 있는 위치가 들어있는 배열 v가 매개변수로 주어질 때, 위의 모든 조건을 만족하는 d 의 최솟값을 return 하도록 solution 함수를 완성해주세요.

제한사항

• l은 1 이상 1,000,000,000 이하의 자연수입니다.
• v에는 가로등의 위치정보가 들어있습니다.
• 가로등의 위치는 0 이상 l 이하의 정수이며, 같은 위치에 2개 이상의 가로등이 있는 경우는 주어지지 않습니다.

• 가로등의 개수는 1이상 1,000 이하의 자연수입니다.

입출력 예

입출력 예 설명

풀이

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 이진탐색을 이용하여 Log(N)으로 풀 수 있음.

이진탐색의 경우 구하는 값중 가장 큰 값을 구할때(상한선), 혹은 구하는 값중 가장 작은 값을 구할때(하한선) 2가지가 있습니다.

다음과 같은 템플릿을 활용할 수 있습니다.

# 템플릿(상한선) - 구하는 값중 가장 큰 값을 구할 때
lower = 어쩌고
upper = 어쩌고

while lower <= upper:
    mid = (lower + upper) // 2
    if is_possibile(mid):
         lower = mid + 1
    else:
        upper = mid - 1
return lower -1

# 템플릿(하한선) - 구하는 값중 가장 작은 값을 구할때
lower = 어쩌고
upper = 어쩌고

while lower <= upper:
    mid = (lower + upper) // 2
    if is_possible(mid):
        upper = mid - 1
    else:
        lower = mid + 1
return upper + 1

가로등 문제는 구하는 값중 가장 작은 구하기 때문에 하한선 템플릿을 이용합니다. 따라서 is_possible 만 짜면 됩니다.

• case1) 만약 첫번째 등에서 왼쪽으로 빛이 뻗을때 0 에 도달하지 못하는 경우는 light를 늘려야 합니다. (is_possible = False인 경우)

• case2) 마찬가지로 마지막 등에서 오른쪽으로 빛이 뻗을 road_length에 도달하지 못하면 light를 늘려야합니다. (is_possible = False인 경우)

• case3) 다음으로, 나머지 램프들을 순서대로 돌면서 light*2를 더해줬을때 다음 램프가 있는 지점까지 도달 못하면 light를 늘려야합니다. (is_possible = False인 경우)

이를 차례대로 구현한 후 템플릿에 대입하면 다음과 같습니다.

def is_possible(lamps, road_length, light):
    # case 1
    if lamps[0] - light > 0:
        return False
    # case 2
    if lamps[-1] + light < road_length:
        return False

    # case 3
    for i in range(len(lamps)-1):
        if lamps[i] + light*2 < lamps[i+1]:
            return False
    return True

# 하한선 템플릿
def solution(lamps, road_length):
    lower = 0
    upper = road_length
    lamps.sort()
    print(lamps)
    while lower <= upper:
        mid = (lower + upper) // 2
        print(mid)
        if is_possible(lamps, road_length, mid):
            upper = mid - 1
        else:
            lower = mid + 1
    return upper + 1