[Programmers] Level 3. 징검다리 건너기

🔗 Problem Link

프로그래머스

---

❔Thinking

• 니니즈 친구들이 징검다리를 건널 수 있도록 한다.
• 모든 디딤돌에는 숫자가 적혀있고(1<= stones <= 200,000,000) 밟을 때마다 1씩 줄어든다.
• 0인 디딤돌은 건너뛰고, 가장 가까운 디딤돌로 건너뛴다. (최대 k칸을 건너 뛸 수 있다.)

---

💻Solution

def check(stones, mid, k):
    cnt = 0
    for s in stones:
        if s <= mid:
            cnt += 1
        else:
            cnt = 0
        if cnt == k:
            return False
    return True

def solution(stones, k):
    left, right = 1, max(stones)
    while left <= right:
        mid = (left+right) // 2
        if check(stones, mid, k):
            left = mid + 1
        else:
            right = mid - 1
    return left

---

🗝️keypoint

1. 징검다리에 적힌 0의 개수가 k개 연속되면 반대편으로 건널 수 없다.
2. 건널 수 있는 사람의 수는 징검다리의 값들 가운데 조건에 만족하는 값과 같은 의미를 가진다.