[Programmers] Pietre miliari

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

overview

Capire il problema stesso era difficile. Le azioni e le decisioni possibili sono:

Rimuovere n pietre dall’array rocks
Trovare la distanza minima tra le pietre rimanenti
- Trovare il massimo tra quei minimi

Calcolare tutte le possibilita’ con la forza bruta non e’ praticabile dato che la distanza puo’ arrivare a 1.000.000.000. Quando la forza bruta non funziona, si puo’ provare la ricerca binaria o il pruning BFS/DFS. BFS/DFS non sembra applicabile qui, quindi proviamo la ricerca binaria con la distanza minima o n come flag.

Soluzione

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

Ci sono vari approcci. Il punto e’ impostare la distanza minima o n come mid, poi contare n calcolando le distanze tra le pietre. ref2 e il mio approccio impostano n come mid. ref1 imposta la distanza minima come mid.

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

5
    # obiettivo della ricerca binaria = distanza minima tra le pietre
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
        # tracciare su quale pietra ci troviamo
14
        current = 0
15

16
        for rock in rocks:
17
            diff = rock - current
18
            # invece di modificare effettivamente l'array rocks,
19
            # cambiamo current per simulare la selezione delle pietre da rimuovere
20
            if diff < mid:
21
                # saltare senza salvare current, "rimuovendo" di fatto la pietra
22
                removeRockCnt += 1
23
            else:
24
                current = rock
25
                # questa pietra non viene rimossa, quindi calcolare la distanza minima
26
                minDistance = min(minDistance, diff)
27

28
        # se ne abbiamo rimosse piu' di n, dobbiamo rimuoverne di meno
29
        # cioe' la distanza minima tra le pietre deve essere piu' piccola, quindi diminuire right
30
        if removeRockCnt > n:
31
            right = mid - 1
32
        # se ne abbiamo rimosse n o meno, salvare la risposta per ora
33
        # entrambi i casi potrebbero contenere la risposta al problema
34
        else:
35
            answer = minDistance
36
            # abbiamo rimosso n o meno pietre,
37
            # quindi aumentare la distanza minima per rimuovere piu' pietre
38
            left = mid + 1
39

40
    return answer

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