징검다리 건너기 - 모노톤 덱으로 O(n) 풀이
·
Data Structures & Algorithms
1. 문제 요약과 제약프로그래머스 64062 징검다리 건너기는 디딤돌 숫자가 0이 되기 전까지 징검다리를 건널 수 있는 최대 인원을 구하는 문제다.징검다리는 일렬로 놓여 있고, 각 디딤돌에는 숫자가 적혀 있다. 한 명이 건널 때마다 밟은 디딤돌의 숫자가 1씩 줄어든다.숫자가 0이 된 디딤돌은 밟을 수 없다. 대신 다음 디딤돌로 한 번에 최대 k칸까지 건너뛸 수 있다.밟을 수 있는 디딤돌이 여러 개면 가장 가까운 디딤돌로만 건넌다.건너는 친구들은 무제한이라고 가정한다.입력 제약은 다음과 같다.stones의 길이: 1 이상 200,000 이하stones의 각 원소: 1 이상 200,000,000 이하의 자연수k: 1 이상 stones의 길이 이하의 자연수예시는 stones = [2, 4, 5, 3, 2, 1..