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

문제 링크

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

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

풀이 - 다른 블로그 참고 

• 우선, stones 배열의 크기가 1이상 200,000이하인데 순차 탐색할 경우 시간 복잡도가 매우 커짐 + 효율성 테스트 존재 
• 따라서 이분 탐색 사용 
• 이진 탐색 범위는 1 부터 최대 건널 수 있는 사람 수 
  • 사용할 수 없는 돌의 개수가 k개 이상이면 이진 탐색의 범위를 낮추고, 정답 갱신 
  • 사용할 수 없는 돌의 개수가 k개 미만이면 이진 탐색의 범위 올림 

• def solution(stones, k):
  # 이진 탐색 범위 최솟값 
    left = 1 
  # 이진 탐색 범위 최댓값 
    right = max(stones)
    answer = 0
  
  # 이진 탐색 
    while left <= right :
      # 사용할 수 없는 블록 수 
      block = 0 
      mid = (left + right) // 2 
  
      for stone in stones :
        if stone - mid <= 0 :
          block += 1
        else :
          block = 0 
  # 사용할 수 없는 블록 수가 k개 이상이면 
        if block >= k :
          break
  # k 보다 작으면 범위 올리기 
      if block < k :
        left = mid + 1
  # k 이상이면 정답 갱신하고 범위 낮추기 
      else:
        answer = mid 
        right = mid - 1 
    return answer

 

+ 2022.05.17 다시 풀이

건널 수 있는 사람 수를 mid 로 설정 

디딤돌에 적힌 숫자 - 건너는 사람 수가 0보다 작거나 같으면 건널 수 없는 디딤돌이므로 block + 1 

0보다 크면 block 수를 다시 0으로 초기화

block 개수가 k 이상이면 건널 수 없으므로 break 

 

따라서 block 개수가 k보다 작으면 사람 수 늘리기

크거나 같으면 사람 수 줄이기

def solution(stones, k):
    answer = 0
    # 건널 수 있는 사람 수 
    start = 0 
    end = max(stones)
    
    while start <= end :
        mid = (start+end) // 2 
        # 연속한 건널 수 없는 디딤돌의 개수 
        block = 0 
        
        for s in stones:
            if s - mid <= 0 :
                block += 1 
            else:
                block = 0 
            
            if block >= k :
                break
            
        if block < k :
        	# 사람 수 늘리기
            start = mid + 1 
        else:
        	# 사람 수 줄이기 
            end = mid -1 
            answer = mid 
            
    return answer