[프로그래머스] 징검다리 건너기 (Python)

1. 문제

programmers.co.kr/learn/courses/30/lessons/64062#qna

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

2. 풀이

 

이분탐색을 적용해서 풀어야했던 문제.

stones 배열 각 원소들의 값은 1 이상 200,000,000 이므로 최대 2억명의 친구들이 건널 수도 있으므로 2중 포문을 돌리면 시간초과가 난다.

 

따라서, 우선 M번째 친구가 건넜는지 확인하기 위해 M-1번째까지 건넌 상황을 살펴본다.

모두 잘 건넜으면 (cnt < k) first = mid + 1

그렇지 않으면 (cnt >= k) last = mid-1 해서 범위를 좁힌다.

 

모든 탐색을 마쳤으면 first를 반환

 

 

3. 코드

def search(mid, stones, k):
    cnt = 0
    for i in range(len(stones)):
        if stones[i] <= mid:
            cnt += 1
        else:
            cnt = 0
        if cnt >= k:
            return False
    return True


def solution(stones, k):
    answer = 0
    first = 1
    last = max(stones)
    
    while(first <= last):
        mid = int((first + last) /2)
        
        if(search(mid, stones, k)==False):
            last = mid - 1
        else:
            first = mid + 1
    return first

---

💡참고

tech.kakao.com/2020/04/01/2019-internship-test/

2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설