프로그래머스 Level 3 징검다리건너기

징검다리건너기 (프로그래머스 Level 3)

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

문제를 보고 느낀 점은
이번 문제의 답은 ‘최대 가능 수치’와 ‘최소 가능 수치’가 이미 정해져 있으며
그 사이에서 답을 구하는 문제라고 생각하였다
또한, 일일이 반복문을 돌다가는 시간 초과가 발생할 수 있다고 생각하여
‘이진탐색’을 적요하여 풀어보았다

1. 아무리 돌이 적더라도 stones의 최소 수치 만큼의 사람 수는 건널 수 있다
   ex ) 2 1 3 4 -> 최소 1사람은 건널 수 있음
   
2. 아무리 돌이 많더라도 stones의 최대 수치 만큼이 사람이 건널 수 있는 최대 수이다
   ex) n, n-1, 5 ,… -> 5가 제일 크다면 5까지의 사람 수만큼은 건널 수 있다
   

따라서 이진탐색을 ‘적용’해야 겠다고 생각한 뒤
이후 k를 적용하는 로직을 생각하였다

‘k’만큼 ‘연속해서’ 뛸 수 있으므로
반복문에서 ‘현재 진행중인 중간값’만큼 각 돌의 개수를 빼주고
‘뺀 결과’가 0이하라면 해당 돌은 ‘뛰어넘어야’하는 걸로 판정하였다
이후, 그 ‘뛰어넘어야 하는 것’이 ‘연속해서’ k를 넘어서면
실패 처리하였다

1. 성공 시, left를 mid + 1로 설정하고 더 높은 범위 탐색
   
2. 실패 시, right를 mid - 1로 설정하고 더 낮은 범위 탐색
   

Code

#include <vector>
#include<limits.h>

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    int minV = INT_MAX;
    int maxV = -1;

    for (int s : stones)
    {
        if (s < minV)
            minV = s;

        if (s > maxV)
            maxV = s;
    }

    int left = minV;
    int right = maxV;

    while (left <= right)
    {
        int mid = (left + right) / 2;

        bool isSuccess = true;

        // 중간값을 빼가며 연속해서 k를 통과가능한지 확인하는 로직
        int zeroCount = k;
        for (int stoneCount : stones)
        {
            if (stoneCount - mid <= 0)
            {
                zeroCount--;
            }
            else
            {
                zeroCount = k;
            }

            if (zeroCount <= 0)
            {
                isSuccess = false;
                break;
            }
        }

        if (isSuccess == true)
        {
            // 더 큰 수 검사
            left = mid + 1;
        }
        else
        {
            // 실패시 더 작은 수로 하여 재 검색
            right = mid - 1;
        }
    }

    // 통과가능한 가장 큰 수
    answer = left;

    return answer;
}