프로그래머스 징검다리 건너기 C++

 

문제 설명

소풍 중 일렬로 놓여 있는 징검다리가 있는 개울을 만나 건너편으로 건너려고 한다.

징검다리가 조금 부실해 보여 안전하게 건너기 위해 확인을 해보니

해당 징검다리에는 밟을 수 있는 숫자가 적혀있었다

디딤돌에 있는 숫자는 한 번 밟을 때마다 1씩 줄러든다

디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 가까운 디딤돌로 여러 칸을 건널 수 있다.

단 징검다리는 한명씩 건널 수 있다.

 

디딤돌에 적힌 숫자 배열 stones와 한 번에 건널 수 있는 디딤돌의 최대 칸 수 k가 매개변수로 주어 질떄,

최대 몇 명까지 징검다리를 건널 수 있는지 return 하는 문제이다.

 

풀이

한번에 건널 수 있는 수  k가 연속적으로 0이 된 디딤돌의 개수 보다 작은 경우가되면 더 이상 건널 수 없기에

그 전까지 건넌 사람들의 수를 return 하면 된다.

 

최대  몇 명이 건널 수 있는 찾는 문제로 탐색 범위를 줄여나가는 방법인 이분탐색을 사용하였다

중간 값 mid 값을 만들고

탐색 범위를 절반씩 좁혀가면서 최대 몇명이 건널 수 있는지 찾는다

 

bool biscorss 함수를 만들어

 

 매개변수로 stones 배열과, 최대 건널 수 있는 k , 그리고 중간값 mid을 받아준다.

stones의 사이즈만큼 반복문을 돌려

현재 건널 디딤돌에 중간값을 - 해주었을떄 0보다 작으면

zerocount 를 ++ 해주고

또한 만약 zerocount가 k 이상이 되면 건널 수 없음으로 false를 반환해준다.

그외의 조건인 경우 에는 0이 연속적이지 않은 상태로 zerocount를 0으로 다시 초기화 시켜

mid 명이 건널 경우 stones가 버틸 수 있는지 검사를 해준다.

 

본문 에서는 건널 수 있는 최대 인원을 이분 탐색으로 찾기 위해

건널 수 있는 인원을 left 최소 값과 right 최대 값을 선언해주고

2를 나누어 주어 mid값을 구해준다.

그 다음 위의 위의 함수를 호출하여 검사를 해주고

 

건널 수 있다면 더 많은 인원이 가능한지 확인을 위해 mid에 +1 을 해주어 다시 검사를 해주고

건널 수 없는 상태라면 mid - 1을 하여 인원 수를 차례로 줄여 주며 검사를 한다.

 

left가 right와 동일해지거나 크다면 right의 값이 최대 건널 수 있는 인원으로 구한 값을 return 해주면 된다.

예시

예를 들어

stones = {2,4,5,3,2,1,4,2,5,1,} 

k = 3이라면

left = 1  : 건널 수 있는 최소 인원 (원소에서 가장 작은 값)

right = 5   :  건널 수 있는 최대 인원 (원소에서 가장 큰값)

mid = 3 : 중간 값

 

0, 1, 2, 0, 0, 0, 1, 0, 2, 0 으로  k를 넘어가는 값이 없음

첫 번째 bool 함수 통과 

left = mid + 1

 

0,0,1,0,0,0,0,0,1,0 으로 k 넘어감

두 번쨰 bool 불가능

right = mid - 1

 

 

left = 4 , right 3, 

left >= right 조건 성립으로 while 종료

 

3명 리턴