문제설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오 초등학교의 니니즈 친구들이 라이언 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. 라이언 선생님은 니니즈 친구들이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.

징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다. 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다. 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다. 니니즈 친구들은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다. 니니즈 친구들은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.

디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한 사항

  • 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
  • stones 배열의 크기는 1 이상 200,000 이하입니다.
  • stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
  • k는 1 이상 stones의 길이 이하인 자연수입니다.

예제

stones    [2, 4, 5, 3, 2, 1, 4, 2, 5, 1]
k         3
result    3

접근

  • stones 배열의 크기가 최대 2억이다. 브루트포스로는 해결하기 힘들 것이라고 추정할 수 있다.
  • 건널 수 없는 순간을 어떻게 체크할 것인가?

내가 생각한 풀이

  • 한 번 건널 때 1씩 줄어들기 때문에 stones[i]가 0보다 작은 것들이 연속으로 k번 이상 나오면 그 때는 건널 수 없는 순간일 것이다.
  • 시간 복잡도를 줄이기 위해 탐색을 효율적으로 해야 한다. 이분 탐색을 사용한다.

코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> stones, int k) {
  int answer = 0, left = 0, right = 200000000;
  while(left <= right)
  {
      vector<int> temp_stones = stones;
      int mid = (left + right)/2, space_count = 0, flag = 0;
      for(int i = 0 ; i<temp_stones.size() ; i++)
      {
          temp_stones[i] -= mid;
      }
      for(int i = 0 ; i<temp_stones.size() ; i++)
      {
          if(temp_stones[i] <= 0) space_count++;
          else space_count = 0;
          if(space_count>=k)
          {
              flag = 1;
              break;
          }
      }
      if(flag == 1)
      {
          right = mid - 1;
          answer = mid;
      }
      else
      {
          left = mid + 1;
      }
  }
  return answer;
}