[programmers] 프로그래머스 징검다리 건너기(Python)

(주)그렙

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

(Python)

(글쓴날 : 2020.05.18)

 

---

* programmers, 프로그래머스 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

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

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/64062

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

---

2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

한번 밟을 때마다 디딤돌에 적혀있는 숫자가 1씩 줄어드는 징검다리가 주어지고, 디딤돌의 숫자가 0이 되면 다음 디딤돌로 여러 칸을 건너뛸 수 있지만, 0이 아닐 경우 건너뛸 수 없을 때 징검다리를 건널 수 있는 횟수를 구하는 문제입니다.

단, 한 번에 건너 뛸 수 있는 디딤돌은 최대 k개 입니다.

 

저의 경우, 이분 탐색을 적용하였고, Python을 사용했습니다.

디딤돌에 적혀있는 숫자의 최대 크기가 200,000,000이므로, 이분 탐색의 최댓값을 200,000,000으로 잡아 이분 탐색하는 mid 값만큼 디딤돌들의 숫자를 빼가며 k만큼 건너뛰어 징검다리를 건널 수 있는지의 여부를 체크해 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

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

---