[프로그래머스] [BinarySearch] 가로등 (201008)

 

1. 문제 설명

본 문제는 두 가지 방법으로 풀 수 있습니다. PR을 올리실 때에는 두 방법을 모두 올려주세요.

1. 그리디를 이용해 푸는 방법 - O(N) 소요(이는 sorting 에 들어가는 시간복잡도는 제외한 수치임)
2. 이진 탐색을 이용해 푸는 방법 - O(NlogN) 소요

이진 탐색이 무엇인지 모르겠다면? 앞선 collab 노트를 참고해보세요!

---

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

---

입출력 예

lvoutput

15	[15,5,3,7,9,14,0]	3
5	[2,5]	2

입출력 예 설명

입출력 예 #1
d가 3보다 작은 경우(아래 그림의 경우 d = 2) 다음과 같이 밝히지 못하는 부분이 생기게 됩니다.

따라서 모든 길을 밝게 비추기 위한 d의 최솟값은 3이 됩니다.

 

 

 

입출력 예 #2
d가 2보다 작은 경우(아래 그림의 경우 d = 1) 다음과 같이 2 위치에 있는 가로등이 길의 시작 부분을 밝히지 못하게 됩니다.

따라서 모든 길을 밝게 비추기 위한 d의 최솟값은 2가 됩니다.

 

 

 

2. 풀이 

 

 

1) Greedy 로 접근 (시간복잡도 O(N)

각 가로등 사이의 차를 구하고 그 중 가장 큰 간격을 기준으로 가로등 빛 범위 정하기 

 

 

1-1) 틀린 나의 풀이 

def solution(road_length, locations):
    
    if road_length not in locations:
        locations.append(road_length)
        
    if 0 not in locations:
        locations.append(0)

    locations.sort()
    d_list = []

    for idx in range(len(locations)-1):
        gap = locations[idx+1] - locations[idx]
        if gap % 2 == 0:
            d_list.append(gap//2)
        else:
            d_list.append((gap//2)+1)
            
    return max(d_list)​

 

이유를 정말 한참... 찾았는데.. 드디어 반례를 찾았다. 

나는 가로등 gap list 를 구할때 맨 첫 숫자와 마지막 숫자를 넣은채 gap 을 구했다.

하지만 이러면 안되는 것이

 

0과 4의 경우에는 가로등이 없기 때문에 해당 숫자를 넣어서 gap list를 만들고 범위를 구하게되면 

 locations (맨 앞끝 넣은 경우) -> [0,2,4]

 gap_list = [2,2]

 

 따라서 d ==> 1 이 되어버린다 !!! (0,4에 가로등이 있다면 정답이지만 이 경우는 아니니까)

 따라서 양 끝에 가로등이 없는 경우는 2로 나눠지면 안되기 때문에,

 마지막 locations이 아니라 d_list 에 바로 넣어줘야한다. ****

 

 

def solution(road_length, locations):
    
    # 0. location 리스트 정렬 
    locations.sort()
    
    # 1. 가로등 빛 범위 리스트 생성
    d_list = []
    
    # 2. 길 시작점에 가로등 없으면, 시작부터 첫 가로등 범위 바로 d_list에 넣기 
    if 0 not in locations:
        d_list.append(locations[0]) # 0~ 첫가로등 범위 = 첫가로등위치 
        
        
    # 3. 길 끝점에 가로등 없으면, 마지막 가로등 부터 끝까지 범위 바로 d_list에 넣기 
    if road_length not in locations:
        d_list.append(road_length - locations[-1]) # 전체 길 길이 -  마지막 가로등 
        
        
    # 4. 나머지들은 가로등 사이 간격이니까 //2 해주기 
    for idx in range(len(locations)-1):
        gap = locations[idx+1] - locations[idx]
        if gap % 2 == 0:
            d_list.append(gap//2)
        else:
            d_list.append((gap//2)+1)
        
    return max(d_list)

 

하지만 해당경우는 무조건 마지막에 max 를 하기 때문에 o(n) 의 시간복잡도가 걸릴 수 밖에 없다. 

따라서 max 부분을 Binary search 로 바꿔서 시간 복잡도를 조금이나마 줄이려 함 ! 

 

 

2) Binary search (시간복잡도 O(NlogN))

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


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

    lower = 1
    upper = road_length
    while lower <= upper:
        mid = (lower + upper) // 2
        
        ### 해당 범위가 가능하더라도 최소값을 찾기 때문에 ***
        if is_possible(road_length, locations, mid): 
            upper = mid - 1 # 최대값 나추기
        else:
            lower = mid + 1 # 최소값 올리기
    return upper + 1

 

일반적으로는 원하는 최적의 값을 찾으면 반환하는게 binary 이지만

해당 문제는  가장 작은 최적의 값을 찾는게 목표니까 최적 값을 찾아도 계속 진행한다. 

그러다가 탐색 최소값이 최대값을 넘어가는 순간 (최적 값 중 가장 최소값까지 간 상황)

midnum 이 아니라 upper(최대값에서) 1을 더해 준것이 우리가 찾는 최적의 값중 가장 작은 값이다. 

 

 

 

반대로 최대 값을 구하는 경우는 어떻게 짜아하나

 

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

 

여기선 반대로 lower(최소값에서) 1을 더해 준 것이 최적의 값중 가장 큰 값이다 

 

 

 

 

3. 정리 

일단 직관적으로 greedy / sort로 풀어보기 

만약 수 탐색인데 런타임에러 걸린다 하면 이진탐색 

최소, 최대 조건있으면 while lower <= upper 로 돌리고 

최대면 : lower -1 / 최소면 : upper +1 로 반환 !!!

 

 

반대 경우의 문제는 

huidea.tistory.com/112

[백준][binary search] 랜선 자르기 python (200928)