64062: 징검다리 건너기

Link : programmers.co.kr/learn/courses/30/lessons/64062

---

1. 문제

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

  • 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
  • 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
  • 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.

  니니즈 친구들은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
  니니즈 친구들은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.

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

 

---

2. 문제의 조건

• 1 <= stones <= 200,000 (바위의 길이)
• 1 <= n <= 200,000,000 (바위 숫자)
• 1 <= k <= len(stones)

 

---

3. 문제 접근

• 시간 복잡도
  
  배열의 크기도 20만에다가 정담의 범위도 최대 2억이기 때문에 범위가 상당히 넓습니다.
  해당 문제는 이분 탐색(이진 탐색)을 이용하여 해결해야합니다.
  
  범위를 조절해가며 값을 찾는 이분탐색의 파라메트릭 서치가 있습니다.

 

• 아이디어
  
  제가 생각한 정석적인 방법은 모든 stones에서 1씩 뺀 후, 연속된 0이 k개 이상일 경우 그 k가 답이라고 하였습니다.
  하지만, 이 방법을 사용하기엔 2억을 빼야하며 20만의 길이를 탐색해야하므로 결코 시간내에 해결 할 수 없습니다.
  
  QnA를 보던 중 이분탐색이라는 큰 힌트를 얻게 되었습니다.

 

---

4. 풀이 방법

• 정답의 범위는 min(stones), max(stones) 사이에 있습니다.
• 이분 탐색으로 stones - (s + e) // 2 을하여 최대로 이어지는 0의 개수를 파악합니다.
• 만약 연속되는 최대 0의 개수가 k보다 높을경우 e를 m으로 지정하고 만약 0의 개수가 k보다 낮을 경운 s = m + 1로 지정합니다.
  (사실상 값이 만족하는 최대 k를 이분탐색으로 구하는 것이므로 e = m - 1를 하면 최대값이 줄어들게 되어 문제가 풀리지 않습니다.)
• 이렇게 탐색한 s점이 정답입니다.

 

---

5. 소스코드

• cjw-git.tistory.com/143

 

---

 

cjw.git@gmail.com