징검다리 건너기

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

Explanation

initial wrong solution where I was setting wrong condition for if

def solution(stones, k):
    start = 0
    end = 200000000

    while start <= end:
        mid = (start + end) // 2
        temp = [0 if i - mid < 0 else i - mid for i in stones]
        hola = 0
        flag = False
        for num in temp:
            if num <= 0:
                hola += 1
                if hola > k:
                    flag = True
                    break
            else:
                hola = 0
        if flag:
            end = mid - 1
        else:
            start = mid + 1

    print(start)
    return start

It should be if hola >= k. This is because let’s say if we have k=3, once we encounter 3 consecutive 0s, then our hola value is 3 and greater and that is condition for our flag. It is not hola>3 just look at the question diagram. Flag should be raised when we see k or more times of consecutive 0s.

Also, don’t forget to make a copy of stones list each time you do the binary search or else if you keep using the same stones list on and on, at the start of the search it is all full of 0s. So your search will be wrong as you will be searching with list of 0s.

Improve time complexity

Also!! To reduce runtime, you should not blindly copy the maximum boundary that the question gives to you like if it is stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다. then your end shouldn’t blindly be 200,000,000. We can just take max(stones) because that is the highest we can get for any given stones list.

If that still doesn’t fix runtime, look at your time complexity. My original code had some runtime issues so let’s see

def solution(stones, k):
    answer = 0
    start=1
    end = 200000000
    while start<=end:
        mid = (end+start)//2
        stones_copy = [stone - mid if stone-mid >=0 else 0 for stone in stones]
        count=0
        flag=False
        for stone in stones_copy:
            if stone==0:
                count+=1
                if count>=k:
                    flag=True
                    break
            else:
                count=0
        if flag:
            end=mid-1
        else:
            start=mid+1
    return start

Notice for very long stones list, I need to make a stones_copy each time for each search (O(n) time complexity) and iterating each element in that stones_copy again (O(n) time complexity). So it is actually O(2n) time complexity.

So how can I make this just O(n) time complexity? Well we actually don’t need to make a stones_copy list each time for a cycle of binary search. We can straight away iterate each stone in stones list and if that stone minus our guess of number of friends is less than or equal to 0, we increment count.

my fixed solution

def solution(stones, k):
    start = 0
    end = 200000000

    while start <= end:
        mid = (start + end) // 2
        temp = [0 if i - mid < 0 else i - mid for i in stones]
        hola = 0
        flag = False
        for num in temp:
            if num <= 0:
                hola += 1
                if hola >= k:
                    flag = True
                    break
            else:
                hola = 0
        if flag:
            end = mid - 1
        else:
            start = mid + 1

    print(start)
    return start

count>k or count >=k??

And then, there is this issue of is it count>k or count >=k.

my question to gpt

ah ok so the way that i was count hola is that if k is 3 and hola is incremented until value 3, that means there are 3 consecutive 0s already which means we cannot continue

reply back was

Yes, exactly! In this problem, hola represents the number of consecutive 0s encountered in temp. When hola becomes equal to or greater than k, it means that you have found a position where it is not possible to continue jumping k consecutive stones, as there are already k or more consecutive 0s.

By checking hola >= k, you ensure that you detect this condition correctly and stop the loop when it is not possible to continue jumping k consecutive stones.