[2019 카카오 개발자 겨울 인턴십] 징검다리 건너기 (LV3)

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

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

 

이분탐색은 많이 풀어봐야 감을 잡을 것 같담

 

[풀이]

1. 최대로 이동가능한 사람 인원을 찾는다 

- 가장 많은 횟수로 디딜수 있는 디딤돌의 수가 된다.

2. 중간값 N을 구한다. 

- 이 의미는, N 번째의 사람이 넘어갈때를 확인하는 것이 된다.

 

3. stone-mid 가 0 이하인지 확인한다.

- stone-mid 는 N 번째 사람이 넘어갈때의 stone 상태값이 된다.

3-1. 0 이 된다면 패스해야하므로 cnt++  해준다.

 

4. cnt가 k 이상이 되는지 확인한다.

4-1. 이상이라면, N번째 사람은 넘어갈 수 없는 것이므로 min_p ~ N-1 의 사람으로 다시 탐색한다.

4-2. 이하라면, N번째 사람은 통과한다는 것이므로 answer 에 N을 세팅해주고, N+1 ~ max_p 로 다시 탐색한다.

 

[코드]

def solution(stones, k):
    answer = 0
    min_p = 1
    max_p = max(stones)
    
    while min_p <= max_p:
        mid = (min_p + max_p) // 2
        cnt =0
        
        for stone in stones:
            if stone - mid <= 0:
                cnt += 1
            else:
                cnt = 0

            if cnt >= k:
                break
        if(cnt < k):
            min_p = mid+1
        else:
            answer = mid
            max_p = mid-1
    
    return answer

 

[정확성 통과/ 효율성 불통]

def solution(stones, k):
    answer = 0
    while True:
        cnt = 0
        for i in range(len(stones)):
            if(stones[i]>0): 
                cnt = 0
                stones[i]-=1
            else:
                cnt = cnt+1
                
            if cnt == k:
                return answer
        answer+= 1
    
    return answer