[프로그래머스 > Lv4] 징검다리

프로그래머스

 

1. 문제

[입력]

출발지점부터 도착지점까지의 거리 distance

바위들이 있는 위치를 담은 배열 rocks

제거할 바위의 수 n

 

[결과]

바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return

 

2. 풀이

문제의 카테고리에서 알 수 있듯이 이분탐색을 이용해 풀 수 있는 문제입니다.

 

시작점은 0, 끝점은 distance로 두고 중간값 mid는 바위들 사이의 최대 거리를 의미한다고 합시다.

그럼 이분 탐색의 범위를 정하는 조건은 무엇일까요? 🤔

 

이 때, 입력값으로 주어진 제거할 바위의 수 n을 사용할 수 있습니다.

바위들 사이에 가능한 최대 거리가 mid이기 때문에 mid가 될때까지 그 중간 바위들은 제거할 수 있음을 알 수 있습니다.

 

그리고 이렇게 제거된 바위의 개수가 n보다 클 경우에는 제거될 수 있는 바위의 개수를 줄여야 하기 때문에

이분 탐색의 범위를 왼쪽(left ~ mid-1)으로 나누며, 그러지 않을 경우에는 오른쪽(mid+1 ~ right)으로 나누어줄 수 있습니다.

 

이를 코드로 간략히 나타내면 아래와 같습니다. 👇🏻

left, right = 0, distance
while left < right:
	mid = (left+right)//2
    skip = // 제거될 수 있는 바위의 개수
    if skip > n:
    	right = mid
    else:
    	left = mid+1

 

이제는 제거될 수 있는 바위의 개수를 구해야 합니다.

각 바위 사이의 거리들을 합하면서 건너뛸 수 있는 바위의 개수를 구해보도록 하겠습니다.

 

바위 사이의 거리를 이용해야 하기 때문에 먼저 rocks 배열을 이용해 새로운 배열을 만들어주도록 하겠습니다.

🌹 이때, 시작점은 0, 끝점은 distance여야 한다는 사실에 유의해주세요.

 rocks.sort()
diff = []
for i in range(1,len(rocks)):
    diff.append(rocks[i]-rocks[i-1])
diff = [rocks[0]] + diff + [distance-rocks[-1]]

 

제거될 바위의 개수를 구하는 코드는 아래와 같습니다.

def countSkip(diff, mid):
    cur, skip = 0, 0
    for d in diff:
        cur += d
        if cur > mid: cur = 0
        else: skip+=1
    return skip​

 

3. 코드

Python

def solution(distance, rocks, n):
    rocks.sort()
    diff = []
    for i in range(1,len(rocks)):
        diff.append(rocks[i]-rocks[i-1])
    diff = [rocks[0]] + diff + [distance-rocks[-1]]
    left, right = 0, distance
    
    while left < right:
        # 각 지점간의 최소 거리
        mid = (left+right)//2
        skip = countSkip(diff, mid)
        if skip > n: right = mid
        else: left = mid+1
            
    return left

def countSkip(diff, mid):
    cur, skip = 0, 0
    for d in diff:
        cur += d
        if cur > mid: cur = 0
        else: skip+=1
    return skip