[프로그래머스] 징검다리 건너기 | 자바스크립트 | Lv.3 | 2019 카카오 개발자 겨울 인턴십

문제

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

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

 

풀이

정확성O, 효율성X 코드

function solution2(stones, k) { // 정확성만 통과
  let start = 1,
    end = Math.max(...stones);
  while (start <= end) {
    const mid = Math.floor((start + end) / 2);
    const temp = stones.map((num) => num - mid);
    let count = 0;
    for (const num of temp) {
      if (num <= 0) count++;
      else count = 0;
      if (count >= k) break;
    }
    if (count >= k) end = mid - 1;
    else {
      start = mid + 1;
    }
  }
  return start;
}

정확성O, 효율성O 통과 코드

function solution1(stones, k) { // 효율성 통과
  let start = 1,
    end = 200000000;
  while (start <= end) {
    const mid = Math.floor((start + end) / 2);
    let count = 0;
    for (const num of stones) {
      if (num - mid <= 0) count++;
      else count = 0;
      if (count >= k) break;
    }
    if (count >= k) end = mid - 1;
    else {
      start = mid + 1;
    }
  }
  return start;
}

수의 범위가 20만까지 가기 때문에 단순히 반복문만 돌려서 하기엔 시간 초과가 날 거라는 걸 알 수 있다. 그렇기 때문에 딱 봤을 때 이분탐색을 사용해야 할 것 같았다.

stones배열 원소들의 범위는 1 이상 200,000,000 이하인 자연수라고 주어졌기 때문에 start를 1로, end를 200,000,000으로 두고stones를 한번 돌때마다 mid값을 갱신한다.

for (const num of stones) {
  if (num - mid <= 0) count++;
  else count = 0;
  if (count >= k) break;
}

이 부분은 연속된 0의 최대 개수를 구하는 로직이다. stones의 각 원소에 mid를 뺀값이 0보다 작거나 같을 경우 mid가 해당 원소보다 크거나 같다는 뜻이다. 1부터 200,000,000사이를 범위로 해서 mid를 계속 갱신해서 stones에 반영해보고 mid의 왼쪽 범위를 탐색해야 할 지 오른쪽 범위를 탐색해야 할지 선택하는 방식이다.

count가 k보다 클 경우, end를 mid - 1로 왼쪽(아래) 값을 탐색하도록하고, count가 k보다 작을 경우, start를 mid + 1로 오른쪽(위) 값을 탐색하도록 한다. 

---

아래 예제를 통해 알아보자.

입출력 예 #1

첫 번째 친구는 다음과 같이 징검다리를 건널 수 있습니다.

첫 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
두 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.

두 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
세 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.

세 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
네 번째 친구가 징검다리를 건너려면, 세 번째 디딤돌에서 일곱 번째 디딤돌로 네 칸을 건너뛰어야 합니다. 하지만 k = 3 이므로 건너뛸 수 없습니다.

따라서 최대 3명이 디딤돌을 모두 건널 수 있습니다.

---

만약 mid가 200,000,000부터 계속 1/2씩 줄여와서 5가 됐다고 치자. 그럼 num - mid가 <= 0인 연속적인 부분의 최대 길이는 전체 길이가 될거다.
여기서 다시 end를 5 - 1 = 4 로 갱신하면 mid는 2가 된다. 그럼 num - mid가 <= 0인 연속적인 부분의 최대 길이는 5번째의 2 1 이 부분일거다.
2 < k이므로 start = mid + 1 = 3으로 갱신하면 mid는 3이 된다. 그럼 num - mid가 <= 0인 연속적인 부분의 최대 길이는 4번째의 3 2 1 이 부분일거다. 3 >= k이므로 end를 mid - 1 = 2로 갱신되고 start <= end를 만족하지 못해 while문을 빠져나오게 된다.

---

 

나는 이분탐색을 인덱스에서 활용하는 법만 알았는데 이런식으로 원소들의 최대 최소값을 기준으로 탐색할 수도 있다는 걸 알았다. 다음에 요런 문제 나오면 제대로 활용해봐야지 ..