[카카오] 징검다리 건너기

---

문제 링크

---

def check(stones, num, k):
    cnt = 0
    for i in range(len(stones)):
        if stones[i] <= num:
            cnt += 1
            if cnt >= k:
                return False
        else:
            cnt = 0
    return True
        
def solution(stones, k):
    left = 0
    right = 200000000

    while left <= right:
        mid = (left + right) // 2 # 학생 수
        if check(stones, mid, k):
            left = mid + 1
        else:
            right = mid - 1
        
    return left

• 이진탐색 문제

이진탐색을 무엇을 기준으로 풀어야할지를 생각하는 것이 관건인 듯하다.
카카오 테크 블로그 문제 해설
0이 연속으로 K개가 나오는 구간이 있는 경우 : M번째 친구는 징검다리를 건널 수 없다.

배열 원소의 최댓값이 200,000,000이기 때문에

left = 0
right = 200000000

으로 두면 되겠다.
mid = (left + right) // 2
mid를 M번째 친구라고 하고 해당 친구가 징검다리를 건널 수 있는지 확인ㄴ하면 된다.
만약 건널 수 없다면 그 뒤 친구들도 건널 수 없다. 앞의 친구들을 확인해야 한다
👉 right = mid - 1
건널 수 있다면 뒤의 학생들을 확인해야 한다.
👉 left = mid + 1

해당 코드는 다음과 같다.

    while left <= right:
        mid = (left + right) // 2 # 학생 수
        if check(stones, mid, k):
            left = mid + 1
        else:
            right = mid - 1

이제 건널 수 있는지 확인하는 함수를 만들어보자.
나는 check 함수를 따로 정의해서 작성했다.
먼저 check 함수로 전달해야하는 파라미터는
(stones 배열, 건널 학생 수, k) 이다.

def check(stones, num, k):
    cnt = 0 # 밟을 수 없는 디딤돌 개수
    for i in range(len(stones)):
        if stones[i] <= num:
            cnt += 1
            if cnt >= k:
                return False
        else:
            cnt = 0
    return True

밟을 수 없는 디딤돌의 연속 개수가 k 이상이면 False를 리턴하도록 작성하였다.

---

일단 내가 처음에 작성했던 코드는
정확성만 100 효율성은 0이었다

def solution(stones, k):
    answer = int(1e9)
    for i in range(len(stones) - k + 1):
        answer = min(answer, max(stones[i:i+k]))
    return answer

짧아보이지만, k 만큼의 배열 원소들을 계속해서 비교해야 한다.

이분 탐색 떠올리기 넘 쉽지 안쿠나 . ..
기준을 뭐로 해야할지도 떠올리기가,,
이분탐색에 약한가보오