프로그래머스 징검다리 건너기(feat.속도개선기)

정답코드는 맨 하단에 기입해놓았다.

오랜만에 효율성에서 애먹은 문제를 만나 나중에 까먹지 않으려고 포스팅한다.
먼저 stones의 배열 크기와 원소 크기를 보고 그냥 구현하면 시간초과 나겠거니 해서 이분탐색으로 풀었다.
범위가 많고 배열을 순회하며 값을 찾아야할땐 이분탐색이 적절한 케이스가 많은것 같다.

문제

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

문제풀이방식(이분탐색)

1. 스톤의 원소들이 모두 1이라면? 한사람밖에 건널 수 없다 하지만 2억이라면? 2억명의 친구들이 건널 수 있다. 따라서 배열 stones의 최소 원소가 건널 수 있는 친구의 최저(left), 최대원소가 건널 수 있는 친구의 최대(right)인것이다.
2. stones 배열을 copy하고, 중간값(mid)을 구해 배열을 순회하면서 mid를 빼준다.
3. 순회하면서 각 요소가 0이하가 될 경우 count를 해주고 0이하가 아니라면 변수를 다시 0으로 초기화시켜준다.(나는 코드에서 변수 stepCheck를 사용하였다.)
4. count === k가 될 경우 건널 수 없기 때문에 해당 mid는 너무 큰값이다. 따라서 right를 mid-1을 하여 줄여준다.
5. count !== k가 될 경우 건널 수 있기 때문에 더 큰값이 존재하는지 알아보기 위해 left를 mid +1을 하여 증가시켜준다.
6. 이때 left에 결국 건널 수 있는 최댓값이 담긴다.

그러나 통과하지 못했다

1. 런타임 에러

근데 왠걸 효율성에서 시간초과가 아니라 런타임에러가 났다. 런타임에러는 예상하지 못해서 적잖이 당황했는데 코드를 보자마자 왠지 math 함수 때문일것 같다는 느낌이 강하게 들었다.

위에 기입해놓은 문제 풀이방식 1번에 따라 다음과 같이 stones배열에서 min, max 값을 찾아 아래와 같이 작성하였는데

let left =  Math.min(...stones);
let right = Math.max(...stones);

큰배열에 대하여 math함수를 사용해 구하려고 하면 범위 에러가 난다고 한다

Maximum call stack size exceeded with Math.min and Math.max

let left = 1;
let right = 200000000; //그래서 그냥 조건값으로 고쳐주었다.

2. 시간초과

그래도 난 해결하지 못했고..

const mid = Math.floor((right + left) / 2);
const steppedStones = stones.map((elem) => (elem -= mid));

for (let elem of steppedStones) {
  if (elem <= 0) {
    stepCheck += 1;
  } else {
    stepCheck = 0;
  }
  if (stepCheck === k) {
    break;
  }
}

나는 이런식으로 map을 이용해 stones의 원소를 변형한 새로운 배열을 steppesStones에 담아 사용중이었는데 혹시 map 속도가 느린가??하여 찾아보았더니

[JS] 반복문 (for, forEach 등) 속도 비교

정말 느린게 맞았다! 의외로 for문이 제일 빨랐다.

참고로 [].concat이나 slice도 해보았는데 시간초과가 났다.

그래서 for문으로 index를 순회하며 일일히 넣어주었는데도 시간초과가 났다.

const steppedStones = [];
for(let i=0; i<stones.length; i++){
    steppedStones[i] = stones[i];
}

난 다시 또 배열 복사엔 어떤게 가장 빠른지 찾아보기 시작했고 감사하게도 테스트해주신 분들이 많이 계셨다.

new Array로 미리 고정 배열을 만들어 단순 대입해주는것이 가장 빠르다는것을 알게되었다.

The Fastest Way to Clone Javascript Arrays

const steppedStones = new Array(stones.length);
for (let i = 0; i < stones.length; i++) {
  steppedStones[i] = stones[i];
}

또, 이 과정에서 각 원소에 mid값을 빼주는 부분과 for of문으로 연속된 0이하의 원소가 있는지 체크해주는 부분을 합쳐 같은 for문 안에서 실행되게 하였다.

최종코드

function solution(stones, k) {
  let answer = 0;
  let left = 1;
  let right = 200000000;

  while (right >= left) {
    let stepCheck = 0;
    const mid = Math.floor((right + left) / 2);
    const steppedStones = new Array(stones.length);
    for (let i = 0; i < stones.length; i++) {
      steppedStones[i] = stones[i];
    }
    for (let i = 0; i < steppedStones.length; i++) {
      steppedStones[i] -= mid;
      if (steppedStones[i] <= 0) {
        stepCheck += 1;
      } else {
        stepCheck = 0;
      }
      if (stepCheck === k) {
        break;
      }
    }

    if (stepCheck === k) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return (answer = left);
}

---

c++로 풀땐 뭐가 더 빠른지 고려해서 풀었으면서 왜 js에선 생각없이 풀고있었는지 매우 반성중이다… 역시 기본이 중요하다는걸 다시 깨달았다!