[Programmers] 징검다리 건너기

코딩테스트 연습 - 징검다리 건너기

---

  밟을 수 있는 횟수가 정해진 돌들로 이루어진 징검다리를 건널 때 최대 몇 명이 징검다리를 건널 수 있는지를 찾는 문제이다. 이 때 각 징검다리의 돌은 주어진 k 만큼 뛰어 넘을 수도 있다.

 

1. 문제 분석

  문제를 봤을 때 가장 먼저 든 생각은 제한 사항의 숫자들이 상당히 크다는 점이다. stones 배열의 크기는 1~20만 범위이며, stones의 원소 값은 1~2억까지 범위를 갖는다. 따라서 해결 방법이 입출력 예시처럼 한 사람씩 건너지는지 확인하는 것은 O(N*M) 즉, stones.length * stones의 원소 범위 만큼의 시간이 걸리므로 시간초과에 걸릴 것이다. 징검다리 건너기 문제의 경우 Binary Search를 이용하면 O(logN)의 시간복잡도로 문제를 해결할 수 있다.

 

  무엇을 Binary Search해야할지 생각해보자. 사실 문제를 다시 읽어보고 생각해봤을 때 범위를 정해서 줄여나가며 답을 찾을 수 있는 요소는 문제의 답인 징검다리를 건널 수 있는 사람의 수밖에 없다.

 

징검다리를 건너는 죠르디

  그렇다면 사람의 범위는 어디부터 어디까지일까? 나는 범위가 징검다리의 숫자 범위와 거의 유사할 것이라고 예상했다. 한 사람이 징검다리를 밟을 때마다 숫자가 -1되기 때문이다. 이 문제의 포인트는 항상 가장 가까운 돌(0 이상)로 이동해야 한다는 점이다. 즉, 점프를 아무때나 할 수 있는 것이 아니라 0을 만났을 때만 최소 거리로 점프한다는 것이다. 따라서 매 턴마다 0을 제외한 돌의 숫자들은 -1된다.

 

징검다리 (2, 3, 4)와 k값

  징검다리가 (2, 3, 4)라면 k의 값에 상관없이 처음 두 사람은 무조건 첫 번째 돌(2)을 밟게 된다. 이 때 k가 1이라면 뛰어넘기가 불가능하므로, 2명이 지나갈 수 있게 되고, k가 2 이상이라면 하나의 돌이 0이 되어도 뛰어 넘을 수 있다. k가 k의 최대 값인 3라면 모든 숫자가 1씩 매 턴마다 1씩 줄어들다가 징검다리의 최대 값인 4가 0이 될 때까지 뛰어 넘을 수 있다. 따라서 징검다리 (2, 3, 4)의 지나갈 수 있는 사람의 범위는 2~4가 된다.

 

k=3이라 징검다리를 건너지 못하는 스카피

  이제 결정된 사람 숫자에 따라 이 인원이 징검다리를 건널 수 있을지만 확인하면 된다. 징검다리를 건너지 못하는 순간은 0이된 연속된 돌의 갯수가 k개 이상일 때이다. mid명이 건널 수 있는지 확인하려면 mid 명이 건너는 도중에 연속된 0이 k개 미만이어야 한다. 만약 k = 1일 때 mid 명이 건널 수 있는 징검다리는 모든 돌의 값이 mid 값 이상을 가져야 한다. 한 명이 지날 때 마다 모든 돌이 -1되기 때문이다. 즉, mid 이하의 연속된 k개 이상의 돌이 있다면 이들은 mid 명이 건너는 도중에 0이 되어버리므로 mid 명이 건널 수 없는 경로가 되어버린다.

 

2. 코드

function solution(stones, k) {
  const getRange = (array) => {
    let max = 0;
    let min = Number.MAX_SAFE_INTEGER;
    for (let i = 0; i < array.length; i++) {
      if (min > array[i]) min = array[i];
      if (max < array[i]) max = array[i];
    }
    return [min, max];
  }

  const checkStones = (mid) => {
    let cnt = 0;
    for (let i = 0; i < stones.length; i++) {
      if (stones[i] <= mid) cnt++; // mid명이 지나가다가 0이 되는 돌
      else cnt = 0;
      if (cnt === k) return false;
    }
    return true;
  }

  // Binary Search
  let [min, max] = getRange(stones);
  let mid
  while (min <= max) {
    mid = Math.floor((min + max) / 2);
    if (checkStones(mid)) min = mid + 1; // 더 큰 수가 있을 수 있으므로 더 찾는다.
    else max = mid - 1;
  }
  return min;
}