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

문제 이해하기

우리가 원하는 것은 바위를 n개를 제거했을 때 최소 거리가 되는 최대 값을 찾는 것이 목적입니다.주어진 문제의 조건은 아래와 같습니다.

• 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
• 바위는 1개 이상 50,000개 이하가 있습니다.
• n 은 1 이상 바위의 개수 이하입니다.

https://school.programmers.co.kr/learn/courses/30/lessons/43236

문제 해결 방법 설명하기

1. 최소가 되는 최대값 찾기

우리가 원하는 것은 바위를 n개를 제거했을 때 최소 거리가 되는 최대 값을 찾는 것이 목적입니다.

따라서 바위의 숫자가 적다면 완전탐색으로도 해결이 가능하지만, 해당 문제는 바위의 개수가 50,000개이기 때문에 완전탐색으로는 원하는 시간안에 해결이 불가능합니다(50000C2)

 

따라서 다른 방법을 사용해야 하는데 우리가 원하는 것은 최소 거리가 되는 최대 값을 찾는 것입니다.

최소 거리가 되는 최대 값의 MAX는 목적지에서 출발자를 뺀 값임은 자명합니다.

 

따라서 우리는 0 ~ 1,000,000,000의 값이 최소가 되는 최대가 될 수 있는지 판별해야 합니다.

하지만 이 방법도 O(n)의 방식으로 수행한다면 시간안에 풀지 못합니다.

 

따라서 우리는 이분탐색을 통해서 원하는 값을 찾아야 하고, 이분탐색의 빅오는 n*Logn이니 제한시간을 만족할 수 있습니다.

#distance를 사용한 이분탐색 방법
while start + 1 < end:
        mid = (start + end) // 2
        removed_rocks = 0
        startPoint = 0
        
        for i in range(len(rocks)):
            if rocks[i] - startPoint < mid:
                removed_rocks += 1
            else:
                startPoint = rocks[i]
                
        if n < removed_rocks:
            end = mid
        else:
            start = mid

 

2. 최소의 거리가 MID가 될려면 몇 개의 돌을 제거해야 할까?

이분탐색을 통해 최소가 되는 최대의 거리를 정했습니다.

그 이후에는 어떤 돌들 사이의 거리가 최소가 되는 거리보다 짧은지 반별 후 해당 돌을 제거해야합니다.

 

제거 방법은 시작점(0)에서 다음 돌까지의 거리를 구합니다. 해당 거리가 MID보다 작다면 해당 돌을 제거했다고 체크 후 시작점을 고정시키고 다음 돌로 넘어가면 돌을 제거한 것처럼 동작할 수 있습니다.

 

이후 제거한 돌이 N개보다 많다면 end가 mId가되고, N개보다 작다면 start가 min가 되면서 이분탐색을 계속합니다 

#돌들을 시작점으로 정렬
rocks.sort()

#돌들 사이의 거리 판별 후 제거 지점 선택
for i in range(len(rocks)):
    if rocks[i] - startPoint < mid:
        removed_rocks += 1
    else:
        startPoint = rocks[i]

if n < removed_rocks:
    end = mid
else:
    start = mid

 

코드

def solution(distance, rocks, n):
    answer = 0
    rocks.append(distance)
    rocks.sort()
    
    start = -1
    end = distance + 1
    
    while start + 1 < end:
        mid = (start + end) // 2
        removed_rocks = 0
        startPoint = 0
        
        for i in range(len(rocks)):
            if rocks[i] - startPoint < mid:
                removed_rocks += 1
            else:
                startPoint = rocks[i]
                
        if n < removed_rocks:
            end = mid
        else:
            start = mid
    
    answer = start
    return answer


if __name__ == "__main__":
    distance = 25
    rocks = [2, 14, 11, 21, 17]
    n = 2
    print(solution(distance, rocks, n))  # Expected: 4

코드 리뷰

 

배운점 정리하기

처음에는 완전탐색을 생각했다. 하지만 경우의 수가 너무 많아 절대 풀지 못할 것이라는 것을 눈치챘다.따라서 최소의 범위를 빠르게 줄여나갈 수 있어야 하는데 이를 위해 이분탐색을 사용했다.이분탐색의 응용은 무궁무진한 것 같다.배열에서 특정 인덱스의 탐색부터 특정 값을 만족할 수 있는지부터 재미난 것 같다