징검다리 건너기

문제 접근

시간초과가 날 것이 뻔했지만, 달리 방도가 생각나지 않아 완전탐색을 이용해 접근했다.

1. 친구가 건널 때 마다 stones 배열의 값을 1씩 줄입니다.
2. stones 배열의 요소가 0으로 반복되는 지역을 찾고, 그 반복되는 수가 k보다 크거나 같은지 판단합니다.
3. k보다 작고, 무사히 stones 배열 탐색을 마치면 counter에 1을 더합니다.
4. k보다 크거나 같다면,stones 배열 탐색을 중단하고 counter를 리턴합니다.

2번 과정에서 반복되는 0을 스택에 담는 과정을 거쳤는데, 굳이 스택없이 카운터 변수만 써도 될 것 같습니다.

시간 복잡도

최악의 경우 200,000(stones 길이) * 200,000,000(stones 요소 최댓값) ...

stones 길이는 그렇다쳐도, stones 요소 최댓값을 -1씩 줄이는 방법은 도저히 해법이 될 수 없습니다. 하지만 방법이 떠오르지 않았습니다.

문제 풀이1

완전 탐색을 이용한 코드

function solution(stones, k) {
  let counter = 0
  let max = 0
  let stack = []
  while (max < k) {
    stones = stones.map((stone) => {
      if (stone !== 0) return stone - 1
      else return stone
    })
    counter += 1

    stones.forEach((stone, idx) => {
      if (stone === 0) {
          stack.push(0)
          if (idx === stones.length - 1){
               max = Math.max(stack.length, max)
               stack = []
          }
      }
      else {
        max = Math.max(stack.length, max)
        stack = []
      }
    })
  }
  return counter
}

문제 풀이2

접근 방식 변경

결국 몇명의 사람이 징검다리를 건널 수 있느냐를 찾는 것이다.
다시 말해, 1부터 200,000,000 명 까지 중 최대 인원을 찾는 것이다.

정답인 사람 수를 x라고 하고, 임의의 사람 수를 y라고 할 때, y와 징검다리 조건을 통해 x가 y 기준 높은지 낮은지 범위를 알 수 있다.

따라서 이분 탐색으로 O(log200,000,000)을 가지고 해결 가능하다.

가가가가가가가...x불불불불불불...

1. 1부터 200,000,000(stones 요소 최댓값) 까지에 정답이 있으므로 이분탐색을 이용한다.
2. mid값을 구하고 stones를 mid - 1로 뺄셈 하면서, 0이 반복하는 최대 횟수가 k이상인지 조사한다.
3. k이상이면 불가능한 인원이므로 min 부터 mid - 1 범위를 조사한다.
4. k 미만이면 가능한 인원이므로 mid 부터 max 범위를 조사한다.
5. min = max 경우 출력한다.

function solution(stones, k) {
  let answer = 0
  const BS = (min, max, stones) => {
    if (min === max) {
        answer = min
        return
    }

    const mid = Math.round((min + max) / 2)
    let counter = 0

    for (let i = 0; i < stones.length; i++) {
      if (stones[i] - (mid - 1) <= 0) counter += 1
      else counter = 0

      if (k <= counter) break
    }

    if (k <= counter) BS(min, mid - 1, stones)
    else BS(mid, max, stones)
  }

  BS(1, 200000000, stones)
  return answer
}

느낀 점

이분 탐색을 사용해야만 풀 수 있는 문제였다. 다음번에는 문제풀이1 같은 시간복잡도 문제가 발생할 경우, 이분탐색을 고려해봐야겠다.