[프로그래머스] 카카오 - 징검다리 건너기

문제

2019 카카오 개발자 겨울 인턴십 - 징검다리 건너기

https://school.programmers.co.kr/learn/courses/30/lessons/64062

 

 

 

풀이

 

첫 번째 시도

단순히 건넌 사람의 수를 0부터 시작해서 징검다리를 순회하며 무사히 건널 수 있으면 카운트를 하나씩 증가시켰고, 이를 실패할 때까지 반복했습니다.

그러나 일부 테스트케이스에서 시간초과로 실패했습니다.

function solution(stones, k) {
    let answer = 0;
    while(true) {
        let pos = 0;
        let jump = 0;
        
        while(pos < stones.length) {
            jump++;
            if(jump > k) return answer;
            if(stones[pos] > 0) jump = 0;
            stones[pos]--;
            pos++;
        }
        if(jump >= k) return answer;
        answer++;
    }
    return answer;
}

 

두 번째 시도

징검다리를 전부 순회하는 대신 숫자가 0이 아닌 돌들의 인덱스만 따로 모아서 계산하면 좀 더 효율적이지 않을까 싶었으나, 여전히 시간초과로 실패했습니다.

function solution(stones, k) {
  const stonesCopy = [Infinity, ...stones, Infinity];
  let answer = 0;
  const len = stonesCopy.length;
  let possibleStones = Array.from({ length: len }, (v, i) => i).filter(
    (v) => stonesCopy[v] > 0
  );

  while (true) {
    let temp = [];
    for (let i = 0; i < possibleStones.length - 1; i++) {
      const currentStone = possibleStones[i];
      const nextStone = possibleStones[i + 1];
      const diff = nextStone - currentStone;
      if (diff > k) return answer;
      stonesCopy[currentStone]--;
      if (stonesCopy[currentStone] > 0) temp.push(currentStone);
    }
    answer++;
    possibleStones = [...temp, len - 1];
  }
}

 

세 번째 시도

좀 더 근본적인 해결책이 필요하다고 느꼈습니다.

이번에는 건널 수 있는 사람 수를 0부터 시작하지 않고, 이진탐색을 통해 찾고자 했습니다. 최댓값은 stones 배열 원소 중 최댓값으로 잡았습니다.

시간이 훨씬 단축됐으나, 일부 테스트케이스에서 런타임에러로 인해 실패했습니다.

function solution(stones, k) {
  let left = 0;
  let right = Math.max(...stones);

  while (left < right) {
    const mid = Math.ceil((left + right) / 2);
    if (canCross(stones, k, mid)) left = mid;
    else right = mid - 1;
  }

  return left;
}

function canCross(stones, k, numOfFriends) {
  let jump = 0;

  for (let i = 0; i < stones.length; i++) {
    jump++;
    if (stones[i] >= numOfFriends) jump = 0;
    if (jump >= k) return false;
  }

  return true;
}

 

검색해 보니, 배열의 크기가 너무 커 너무 많은 인자를 Math.max()에 전달되었고, 이로 인해 'Maximum call stack size exceeded' 에러가 발생한다는 것 같았습니다.

 

이 문제와 관련해서는 아래 글을 참고해 주시기 바랍니다.

[JS] Maximum call stack size exceeded 에러

 

아래와 같이 최댓값을 찾는 부분을 수정하여 해결했습니다.

function solution(stones, k) {
  let left = 0;
  let right = getMax(stones);

  while (left < right) {
    const mid = Math.ceil((left + right) / 2);
    if (canCross(stones, k, mid)) left = mid;
    else right = mid - 1;
  }

  return left;
}

// 추가된 부분
function getMax(arr) {
  return arr.reduce((max, v) => (max >= v ? max : v), -Infinity);
}

function canCross(stones, k, numOfFriends) {
  let jump = 0;

  for (let i = 0; i < stones.length; i++) {
    if (stones[i] >= numOfFriends) jump = 0;
    else jump++;
    if (jump >= k) return false;
  }

  return true;
}