[프로그래머스] 이분탐색 2. 징검다리

문제

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

코딩테스트 연습 - 징검다리

---

풀이

이분탐색이라고 카테고리가 주어지지 않았다면 몰랐을 것 같다.

어떤 값을 이분탐색할지 고민해봤다. 선형적인값을 선택해야 하기 때문이다.

리턴값(최소값의 최대값)을 선택하려했는데 검증방법이 딱히 떠오르지 않아 이게 맞나? 고민하다

(https://deok2kim.tistory.com/122) 이분이 리턴값을 기준으로 했다는 것을 보고 좀 더 깊이 생각하니 방법이 떠올랐다.

 

1. 최소 1 최대 distance로 두고 리턴값을 기준으로 이분탐색을 진행한다.

2. rocks를 선형으로 탐색하며 mid 즉 일정 거리 이내에 바위가 있는지 확인한다.

   2-1 있다면 그 바위를 없애고 없앤 바위 수를 업데이트한다.

   2-2 없다면 다음 바위를 기준으로 탐색을 계속 진행한다.

3. 없앤 바위의 수가 n보다 크다면 이 값은 불가능한 것이므로 st 를 옮긴다.

...

 

def isPossible(rocks, dist, n):
    rcnt = 0
    
    i = 0
    interval = 1
    while i < len(rocks)-1:
        if rocks[i+interval] - rocks[i] < dist:
            rcnt += 1
            interval += 1
        else:
            i += interval
            interval = 1
        if rcnt > n:
            return False
    
    return True

def solution(distance, rocks, n):
    rocks.sort()
    rocks.insert(0, 0)
    rocks.append(distance)
    
    #이분탐색
    st = 1
    ed = distance
    
    while st <= ed:
        mid = (st + ed) // 2
        if isPossible(rocks, mid, n):
            st = mid + 1
        else:
            ed = mid - 1
        
    return (st+ed)//2

처음에 2-1에서 바위를 없애고 나서 다음 바위를 기준으로 탐색을 진행했다가 2개의 케이스에서만 성공했다.

distance = 10, rocks = [1,2,3,4,5,6], n = 5

의 케이스에서 1,2,3,4를 연속으로 지워야 하는데 1을 지우고 2로 넘어갔기 때문이다.

로직에 맞게 수정했더니 통과했다.

---

다른사람의 풀이

def solution(distance, rocks, n):
    answer = 0
    sorted_rocks = sorted(rocks)
    sorted_rocks.append(distance)
    left = 0
    right = distance
    while (left <= right):
        mid = int((left + right) / 2)
        cnt = 0
        p = 0
        for i in range(len(sorted_rocks)):
            if (sorted_rocks[i] - p < mid):
                cnt += 1
            else:
                p = sorted_rocks[i]
        if cnt > n:
            right = mid - 1
        else:
            left = mid + 1
            answer = mid
    return answer

비슷하다

현재 바위 위치를 p로 저장하여 좀 더 깔끔하게 표현했다.