探索-敷石

1.質問

問題の説明

出発点から遠くに到着点があります.そして真ん中に岩が置いてあります.岩の中のいくつかを取り除きたいです.
例えば、到達点距離25で岩が[2,14,11,21,21,17]点にある場合、2つの岩を除去すると、起点、到達点と岩との間の距離は以下のようになる.
除去された岩の位置の各岩間の距離の最大値.
[21, 17][2, 9, 3, 11] 2
[2, 21][11, 3, 3, 8] 3
[2, 11][14, 3, 4, 4] 3
[11, 21][2, 12, 3, 8] 2
[2, 14][11, 6, 4, 4] 4
上記で求めた距離の最大値のうち、最大値は4である.
始点から終点までの距離、岩石が位置する配列岩石、除去する岩石数nをパラメータとする場合は、n個の岩石を除去した後の各点間の距離の最大値に最大値を返す求解関数を作成します.

せいげんじょうけん

までの到達点までの距離は10000000を超えない.

岩は1個以上50000個以下あります.

nは1以上の岩の個数を下回っている.

I/O例

distance rocks n return
25 [2, 14, 11, 21, 17] 2 4

2.解法

にぶんたんさく

問題では、所定の方法で除去する必要がある岩石を固定し、各点間の距離を最大値にするために、岩石を除去するすべての場合の数を考慮することができる.しかし,二分探索を利用すれば,より容易に問題を解決することができる.問題を逆に考えると,与えられた距離を計算する際にどれだけの岩を除去する必要があるか,各点間の距離がその距離より大きいかどうか,二分探索を適用できる.

コード#コード#

def solution(distance, rocks, n):
    
    import copy
    def cnt_del(rocks, dist): ## rocks와 거리가 주어졌을 때 돌을 몇 개 없애야 하는지 return하는 함수
        new_rocks = copy.copy(rocks)
        del_cnt = 0
        i = 0
        prev = 0
        for rock in new_rocks:
            if rock - prev < dist:
                del_cnt += 1
            else:
                prev = rock
        
        return del_cnt
    
    rocks.sort()
    left = 1
    right = int(distance/(len(rocks)-n+1)) ## 균등하게 나눠졌을 때 max값
    answer = left
    
    while left <= right:
        mid = int((left+right)/2)
        del_cnt = cnt_del(rocks, mid)
        if del_cnt <= n:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
            
    return answer

出典:プログラマーコードテスト練習、二分探索、敷石(https://programmers.co.kr/learn/courses/30/lessons/43236)