[Python] 프로그래머스. 2019 카카오 겨울 인턴 recruit - 징검다리 건너기 (Level 3)

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

프로그래머스

19년 12월 처음 접했을 때는 시간이 없어서 못 풀었고, 이번에 풀었을 때 효율성 13번에서 시간초과가 난 문제.

 

공식 풀이는 이분탐색.

나는 이 문제를 '전체 list 중 k개를 window로 돌면서, 해당 window의 최댓값이 가장 작은 것'을 반환하는 문제라고 봤다.

 

window로 돌 때, 해당 window 모든 값이 0이면 더 이상 강을 건널 수 없다.

모든 값이 0이 되려면, window의 가장 큰 값도 0이 되어야 하기 때문.

 

비슷한 알고리즘으로 푸신 듯한 다른 분의 C++코드.

[알고리즘] 카카오 개발자 겨울 인턴십 코딩 테스트 풀이

 

동일한 로직의 코드로 풀었을 때 실제 시험에서는 통과했고, 공개한 연습문제 테스트에서는 시간초과가 났다고 하는 걸 보니

13번 테스트 케이스의 기준이 올라갔나 보다.

 

 

이분탐색으로 푼 코드