[Programmers] Stepping Stones

https://programmers.co.kr/learn/courses/30/lessons/43236?language=python3

overview

Understanding the problem itself was hard. The available actions and decisions are:

Remove n rocks from the rocks array
Find the minimum distance between remaining rocks
- Find the maximum among those minimums

Computing all possibilities by brute force isn’t feasible since distance can be up to 1,000,000,000. When brute force won’t work, we can try binary search or BFS/DFS pruning. BFS/DFS doesn’t seem applicable here, so let’s try binary search with the minimum distance or n as the flag.

Solution

ref1: https://taesan94.tistory.com/154 ref2: https://deok2kim.tistory.com/122

There are various approaches. The point is to set either the minimum distance or n as mid, then count n while calculating distances between rocks. ref2 and my approach set n as mid. ref1 sets the minimum distance as mid.

1
def solution(distance, rocks, n):
2
    answer = 0
3
    rocks.sort()
4

5
    # binary search target = minimum distance between rocks
6
    left, right = 0, distance
7

8
    while left <= right:
9
        removeRockCnt = 0
10
        mid = int((left + right) / 2)
11
        minDistance = float('inf')
12

13
        # track which rock we're currently on
14
        current = 0
15

16
        for rock in rocks:
17
            diff = rock - current
18
            # instead of actually modifying the rocks array,
19
            # we change current to simulate selecting rocks to remove
20
            if diff < mid:
21
                # skip without saving current, effectively "removing" the rock
22
                removeRockCnt += 1
23
            else:
24
                current = rock
25
                # this rock isn't removed, so compute minimum distance
26
                minDistance = min(minDistance, diff)
27

28
        # if we removed more than n, we need to remove fewer
29
        # i.e., the minimum distance between rocks should be smaller, so decrease right
30
        if removeRockCnt > n:
31
            right = mid - 1
32
        # if we removed n or fewer, save the answer for now
33
        # both cases might contain the problem's answer
34
        else:
35
            answer = minDistance
36
            # we removed n or fewer rocks,
37
            # so increase the minimum distance to remove more rocks
38
            left = mid + 1
39

40
    return answer

https://github.com/naem1023/codingTest/blob/master/bs/pg-30-43236.py