[DAY90] Algorithm : Crossing the Stepping Stones

카카오 채용 연계형 인턴십 기출문제로, 징검다리를 건널 수 있는 최대 인원을 구하는 문제다. 디딤돌의 숫자가 최대 2억까지 주어지기 때문에 단순 시뮬레이션으로는 시간 초과가 발생한다. 이분 탐색(Binary Search)을 활용하여 건널 인원수를 먼저 정하고, 그 인원이 건널 수 있는지 역으로 검증하는 파라메트릭 서치(Parametric Search) 기법이 핵심이다.

---

❓ 문제 분석

• 목표: 징검다리를 건널 수 있는 최대 친구들의 수(N) 구하기.
• 제약 조건:
  • stones 배열의 크기: 최대 200,000
  • 디딤돌의 숫자(값): 최대 200,000,000 (2억)
  • $\rightarrow$ 만약 친구 한 명씩 건널 때마다 돌의 숫자를 1씩 줄인다면, 최악의 경우 2억 번 반복해야 하므로 시간 복잡도 O(M)은 시간 초과가 확실하다. 적어도 O(N)이나 O(log M) 수준의 효율적인 접근이 필요하다.
• 핵심 키워드: "디딤돌의 숫자는 1씩 줄어든다", "0이 되면 밟을 수 없다", "최대 몇 명"

---

💡 풀이 설계

단순히 문제를 푸는 것이 아니라, 시간 효율성을 고려해 접근 방식을 바꿨다.

1. 시도했던 접근 (First Attempt) 🚫

• 처음에는 문제 설명대로 정직하게 구현하려 했다.
• while 문을 돌면서 친구 한 명이 건널 때마다 모든 stones의 숫자를 1씩 빼고, 0이 연속으로 k개가 되면 멈추는 방식이다.
• 하지만 디딤돌의 숫자가 2억이라는 점을 간과했다. 2억 명을 다 검사하려면 연산 횟수가 너무 커져서 채점 시 시간 초과(Time Limit Exceeded)가 발생할 것이다.

2. 최종 해결책 (Binary Search) 💡

• 발상의 전환: "몇 명이 건널까?"를 계산하는 대신, "N명이 건널 수 있을까?"(Yes/No)를 확인하는 문제로 바꿨다.

• 탐색 범위: 최소 1명 ~ 최대 2억 명. 범위가 매우 넓고 정렬된 숫자(인원수) 안에서 답을 찾아야 하므로 이분 탐색(Binary Search)이 제격이다.

• 예상 시간 복잡도: $O(N \log M)$

  • 탐색 범위($M=2억$)를 반으로 쪼개는 횟수: $\log_2(200,000,000) \approx 28회$
  • 각 횟수마다 징검다리 전체($N=20만$)를 한 번 순회하며 검사: $28 \times 200,000 \approx 5,600,000회$ (충분히 통과 가능!)

• 알고리즘 흐름:

  1. left = 1, right = 2억으로 설정.
  2. 중간값 mid명(예: 1억 명)이 건널 수 있는지 확인한다.
  3. 검증 로직: stones 배열을 돌며 mid보다 작은 숫자가 연속으로 k번 나오는지 체크한다.
  4. 건널 수 있다면(True): 답을 저장하고, 더 많은 인원도 가능한지 확인하기 위해 left를 올린다.
  5. 건널 수 없다면(False): 인원이 너무 많다는 뜻이므로 right를 내린다.

---

💻 코드 구현

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    int left = 1;
    int right = 200000000; // 최대 인원 수(2억)
    int mid = 0;

    while (left <= right) {
        mid = (left + right) / 2;
        bool canCross = true;
        int zeros = 0; // 연속된 0의 개수

        for (int stone : stones) {
            // mid보다 작은 돌을 만난 경우
            if (stone < mid) {
                // 연속된 0의 개수 증가
                zeros++;
                // 연속된 0의 개수가 k 이상이면 break
                if (zeros >= k) {
                    canCross = false;
                    break;
                }
            }
            else {
                // 연속된 0을 초기화
                zeros = 0;
            }
        }
        if (canCross) {
            answer = mid;
            left = mid + 1; //무한 루프 방지를 위해 범위 +1
        }
        else {
            right = mid - 1; // 무한 루프 방지를 위해 범위 -1
        }
    }
    return answer;
}

---

🐛 시행착오 및 디버깅

• 문제점: 이분 탐색 구현 중 while 문이 끝나지 않고 무한 루프에 빠지는 현상을 걱정했다.
• 원인: 탐색 범위를 좁힐 때 left = mid 처럼 이미 검사한 값을 다시 포함시키면, 특정 조건에서 범위가 줄어들지 않아 무한 반복될 수 있다.
• 해결:
  • 건널 수 있으면(True): left = mid + 1 (mid는 이미 성공했으니 그 다음부터 검사)
  • 건널 수 없으면(False): right = mid - 1 (mid는 실패했으니 그 이전까지만 검사)
  • 이렇게 검사한 mid를 범위에서 확실히 제외하고, 성공했을 때만 answer 변수에 따로 정답을 저장하는 방식으로 해결했다.

---

✅ 오늘의 회고

항목	내용
유형	이분 탐색 (Binary Search), 파라메트릭 서치
체감 난이도	중 (아이디어 떠올리기가 어렵고 구현은 짧음)
복잡도	시간: $O(N \log M)$, 공간: $O(1)$
새로 배운 것	답을 구하기 어려울 땐 "답을 정해놓고 문제 조건에 맞는지 검사"하는 파라메트릭 서치 접근법이 유효하다는 것을 배웠다.