# 징검다리 건너기(이분탐색) - 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/64062

• 문제

  • 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
  • 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
  • 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.
  • 디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

• 제한사항

  • 징검다리를 건너야 하는 친구들의 수는 무제한 이라고 간주합니다.
  • stones 배열의 크기는 1 이상 200,000 이하입니다.
  • stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
  • k는 1 이상 stones의 길이 이하인 자연수입니다.

• 접근 방법
  • stones 배열 원소 최대값이 200,000,000로 매우 크므로, 시간복잡도를 고려해야함. 이분 탐색 방법을 사용
  • left에 초기 최소값(답이 될수 있는) 1로 초기화, right에 최대값을 max(stones)로 초기화한다.
  • mid 값으로 징검다리를 건널 수 있는 지 확인한다.
    1.건널 수 있으면 mid값을 우선 answer에 저장 후, left 값을 mid+1로 이동시킨다.
    2.건널수 없으면 right 값을 mid-1 로 이동시킨다.
  • 건널 수 있는 최대 명수를 구해야 하므로, left <= right 인 동안 반복한다.

• 파이썬 코드1
  - 이분탐색을 위한 while문
  - for-else문 사용(for 반복문이 break등으로 멈추지 않고 끝까지 실행되는 경우 else문 실행)

def solution(stones, k):
    answer = 1 
    left,right = 1, max(stones)
    
    while left <= right:
        mid = (left + right) // 2
        temp = [x-mid for x in stones]
        cnt = 0
        for stone in temp:
            if stone < 0:
                cnt += 1
                if cnt == k :
                    right = mid - 1
                    break
            else:
                cnt = 0
            
        else:
            answer = max(answer, mid)
            left = mid + 1
            
    return answer

• 효율성 테스트
  테스트 1 〉 통과 (427.18ms, 34.6MB)
  테스트 2 〉 통과 (510.96ms, 34.9MB)
  테스트 3 〉 통과 (482.60ms, 34.9MB)
  테스트 4 〉 통과 (379.00ms, 34.8MB)
  테스트 5 〉 통과 (344.53ms, 34.8MB)

---

처음부터 끝까지 flow를 정확히 이해하지 않으면, 숫자가 꼬일수 있다. for-else문 보다 코드 가독성을 위해 따로 판정 함수를 만드는 방법이 낫겠다.

• 파이썬 코드2
  - n명이 건널수 있으면 True, 못 건너면 False로 판정하는 isPossible 함수를 만들어서 분리시켰다. (가독성 향상 위해)
  - temp 임시저장 리스트를 없애고, stone의 개수와 건널 사람 n을 바로 비교하는 방법으로 바꿨다. (메모리, 시간 효율 올리기 위해)

 def isPossible(n, stones, k):
    blank = 0
    for stone in stones:
        if stone < n :
            blank += 1
            if blank == k : 
                return False
        else:
            blank = 0
    return True
    
    
def solution(stones, k):
    answer = 1
    left, right = 1, max(stones)
    
    while left <= right :
        mid = (left + right) // 2
        if isPossible(mid, stones, k) :
            answer = mid
            left = mid + 1
        else :
            right = mid - 1
    
    return answer 

• 효율성 테스트
  테스트 1 〉 통과 (196.57ms, 18.6MB)
  테스트 2 〉 통과 (226.63ms, 18.5MB)
  테스트 3 〉 통과 (246.11ms, 18.6MB)
  테스트 4 〉 통과 (105.67ms, 18.5MB)
  테스트 5 〉 통과 (119.44ms, 18.6MB)

두번째 방법으로 가독성 뿐 아니라 시간과 메모리효율도 더 좋아졌다.