프로그래머스 가로등 파이썬

문제 설명

서울시에 일직선 모양의 새로운 도로가 생겼습니다. 새로운 도로의 전체 길이는 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 이하의 자연수입니다.

입출력 예

l	v	output
15	[15,5,3,7,9,14,0]	3
5	[2,5]	2

 

---

접근

- 기본적으로 이진탐색의 양상으로 접근

- 가로등 간의 distance를 distance_list에 append

- distance 값은 인접한 가로등 간 거리를 2등분한 값으로 구한다. (거리가 홀수일 경우 +1)

def solution(road_length, locations):
    locations.sort()
    print(locations)
    distance_list = []  # 가로등 사이의 거리

    if 0 < locations[0]:
        distance_list.append(locations[0])

    for x, y in zip(locations[1:], locations[:-1]):
        if (x - y) % 2 == 0:
            distance = (x - y) // 2
        else:
            distance = (x - y) // 2 + 1
        distance_list.append(distance)

    if road_length > locations[-1]:
        distance_list.append(road_length - locations[-1])
        
    return max(distance_list)

 

주의할 점

- locations[0], locations[-1]이 꼭 road의 시작점과 끝점에 있다는 생각이 함정으로 이어진다.
- locations[0], locations[-1] 은 첫번째와 마지막 가로등일 뿐이지, 이들의 위치가 꼭 road의 시작점과 끝점에 있을 필요는 없다.

 

풀이

- distance를 가장 크게 잡아 distance_list에 넣으면, 모든 거리를 다 비출 수 있다.
- 하지만 구하고자 하는 값은, 모든 거리를 다 비출 수 있는 distance 중 가장 작은 값을 구하는 것
- distance_list엔 가로등 사이를 다 커버할 수 있는 distance의 범위가 들어있다. => 이중에서 최소값(min(distance_list))을 구하면, 어떤 곳은 커버하고, 다른 곳은 커버할 수 없는 경우가 발생한다.
- 그렇기 때문에 d_list의 값 중 가장 큰 값을 선택하는 것이 옳다 (가장 큰 값: 가로등 사이가 가장 많이 떨어져 있는 경우의 distance)

 

다른 풀이 : parametric search

def solution(road_length: int, locations: list):
    locations.sort()

    left = 1
    right = road_length

    while left <= right:
        # mid를 빛의 범위로 정의 => 점차 줄여나간다 이진 탐색 처럼
        mid = (left + right) // 2
        if is_possible(road_length, locations, mid):  # True 일 때
            right = mid - 1
        else:
            left = mid + 1
    return right + 1


def is_possible(road_length, locations, light_range):
    if (0 < locations[0] - light_range) or (locations[-1] + light_range < road_length):
        return False
    for i in range(1, len(locations)):
        if locations[i - 1] + light_range < locations[i] - light_range:  # 가로등 간 공백이 생기는 경우
            return False
    return True