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

출처: 프로그래머스 코딩 테스트 연습, [프로그래머스] 징검다리 건너기

풀이

200,000 * 200,000,000을 연산하면 효율성 문제가 아니더라도 시간 초과가 날 거 같아 어떻게 시간을 줄일지 고민했다. 그러면 200,000을 줄이기는 힘들어 보였고 200,000,000 줄일 생각을 했다.주어진 돌에 적힌 수들을 정렬하고 그 정렬한 수를 연산하면 200,000,000에서 200,000로 연산 많이 준다. 하지만 여기서 효율성 문제인 것을 감안하면 그래도 느리다고 생각했고 200,000도 연속적인 숫자이기 때문에 이분탐색을 사용하기 딱 좋아 보여 최종적으로 이분탐색을 사용해 풀면 통과할 수 있겠다는 생각을 했다.

1. 돌들에 적힌 숫자들을 set()으로 중복된 숫자들을 없앤 후 정렬을 해주어 이분탐색을 할 준비를 한다.
2. 이분탐색을 할 때 만약 주어진 숫자보다 현재 돌의 숫자가 작으면 지워지므로(돌이 없어지므로) 디딤돌의 칸수가 1 증가한다. 아닐 경우는 디딤돌이 존재하는 것이기 때문에 디딤돌 칸수를 1로 다시 초기화한다.
3. 만약 디딤돌의 칸수가 주어진 K보다 커지는 순간은 징검다리를 건널 수 없는 경우이기 때문에 빠져나오고 flag에 체크해준다.
4. flag에 따라 어디로 이분탐색을 할지 정하고 반복한다.
5. left는 항상 만족하는 값이고 right는 항상 실패하는 값이기 때문에 항상 만족하며 젤 큰 값은 left에 해당되기 때문에 정렬된 돌의 숫자의 left번째의 숫자가 답이 된다.

코드

def solution(stones, k):
    
    sortedStones = sorted(set(stones))
    
    left, right = 0, len(sortedStones) - 1
    while left + 1 < right: # left <= right 보다 더 명확하다
        mid = (left + right) // 2
        
        count, flag = 1, True
        for stone in stones:
            if stone < sortedStones[mid]:
                count += 1
            else:
                count = 1
            if count > k:
                flag = False
                break
        
        if flag:
            left = mid # left <= right을 할 경우 mid + 1
        else:
            right = mid # left <= right을 할 경우 mid - 1 해줘야하는데 left + 1 < right은 할 필요없어 명확하다.
    
    return sortedStones[left]

느낀점

이진탐색의 while 조건문을 어떻게 해야할 지 left가 닶인지 right가 답인지 헷갈렸는데 이분 탐색(Binary Search) 헷갈리지 않게 구현하기을 보고 많이 배운거 같다. 그리고 이분탐색은 결정문제에서 많이 쓰인다는데 막 와닿지는 않는다. 결정문제는 답이 예, 아니오로 이분탐색의 경우 답의 파라미터가 하나이기 때문에 사용할 수 있는 것 같다.

이전에 풀었던 [프로그래머스] 금과 은 운반하기와 비슷한 유형의 문제인 것 같다. 이분탐색 구현이 아직 익숙치 않아 기억을 되뇌이며 구현했는데 좀더 익숙해질 필요가 있는것 같다. 이분탐색은 충분히 직접 구현하는 문제가 나올 것 같다.