징검다리 건너기

2019 카카오 개발자 겨울 인턴십 (3.징검다리 건너기) | 프로그래머스

문제

---

흐름 생각하기

디딤돌을 밟을 때마다 디딤돌의 숫자가 1씩 줄어든다.
해당 디딤돌의 숫자가 0이 되면 밟을 수 없음 건너뛰어서 가야함.
한번에 건너뛸 수 있는 디딤돌의 최대 칸 수안에 건너뛰어야하므로 최대 몇명까지 징검다리를 건너는지를 구하는 것.

ⓐ 입출력 예시를 보면 뛰어넘을 수 있는 최대 칸 수는 3칸
ⓑ 2 4 5 3 2 1 4 2 5 1 을 첫 번째 사람이 건너게 되면
ⓒ 1 3 4 2 1 0 3 1 4 0 이 되므로 0이 된 디딤돌이 2개 생성되어있다.
ⓓ 0 2 3 1 0 0 2 0 3 0 ▶ 0 1 2 0 0 0 1 0 2 0 ▶ 0 0 1 0 0 0 0 0 1 0 (x)
ⓔ 총 3명이 건너갈 수 있음

---

코드 어떻게 짜야할까

for문이나 while문으로 차례로 돌아가면서 하나씩 차감하는게 제일 먼저 떠오르긴한다. 근데 이러면 문제 난이도가 Lv.3 일리 없긴한데.. 일단 해보자

---

코드 짜보기

막상 코드 짜보니까 연속적으로 0이 나왔을 때를 잘 봐야하는 것같다.
일단 예제코드는 맞추긴 했는데 과연 정답일까. 이렇게 빨리 맞출리가 없는데................
...............응 역시는 역시다

결과는 장렬하게 실패다 ^^!
런타임 에러도 그렇고 타임도 많이 오바된다. while문이랑 for문 때문인가 :(
시간 초과인거 알겠으니까 그만 하라고..
마음이 쓰리다..

---

최종 코드

찾아보니까 이진탐색으로 하는게 제일 효과적이라고 한다. 예전 알고리즘 수업이 생각나서 순간 머리가 아찔했다.. 그렇구나 이건 이진탐색으로 해야하는구나..

아 디딤돌 숫자가 어차피 0이면 건너뛰어야하니까 건너는 순서보단 디딤돌 숫자에 포커스를 맞추는구나.

ⓐ Left는 최소 숫자 1. Right는 stones 원소중에 제일 큰 숫자.
ⓑ Left와 Right를 더해서 2로 나눈 mid 값을 생성한다.
ⓒ stones 원소와 mid값을 빼서 0이하의 값이 나오는지, 그 이상의 값이 나오는지 체크
ⓓ 0이하의 값이 나오는 경우를 ct변수를 통해 체크한 후, k 값과 비교한다.

ct를 계속 0으로 초기화했어야했는데 그러질 못해서 첨에 테스트 케이스 몇 개를 통과하지 못했다
근데 다시보니까 효율성 테스트에서 통과를 못했다.
훑어보니까 mid 계산을 for문에 넣어서 생긴 해프닝이었다. for문 밖으로 mid 계산을 빼주니 통과가 되었다.