징검다리 건너기

문제

---

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

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

 

 

나의 풀이

---

그냥 문제에서 주어진 대로 1명이 지나갈 때마다 디딤돌의 수에서 -1 해주면 O(n^2)으로 시간초과가 난다. 문제의 주어진 조건에서 보면 디딤돌의 수는 1이상 200000000이하의 자연수이므로 정답의 범위는 1이상 200000000이하라는걸 알 수 있다. (모든 디딤돌 수가 200000000이면 200000000명이 건널 수 있으니까)

이처럼 선형자료의 탐색을 할 때는 시간을 줄이기 위해 이분탐색을 사용하면 좋다.

1. l, r 을 각각 1과 200000000으로 초기화 시킨 뒤 이분탐색을 한다.
2. 여기서 탐색하는 수가 정답으로 return할 최대로 건널 수 있는 학생의 수이다.
3. 각 mid값마다 0이하의 수가 연속으로 k개가 되는지를 검사한다.
4. 만약 0이하의 수 k개가 연속된다면 r = mid-1을 해주고, 아니라면 l = mid + 1을 해준다.

 

코드

---

import copy
def solution(stones, k):
    l,r = 1, 200000000
    while l<=r:
        mid = (l+r)//2
        tmp = copy.deepcopy(stones)
        for i in range(len(tmp)):
            tmp[i] -= mid
        cnt = 0
        flag = 0
        for i in range(len(tmp)):
            if tmp[i] > 0:
                cnt = 0
            else:
                cnt += 1
            if cnt == k:
                flag = 1
                break
        if flag == 1:
            r = mid - 1
        else:
            l = mid + 1
    return l