[프로그래머스] LV.3 징검다리 건너기 (JS)

문제

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. "라이언" 선생님은 "니니즈 친구들"이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.

• 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
• 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
• 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.
  "니니즈 친구들"은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
  "니니즈 친구들"은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.

디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한

• 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
• stones 배열의 크기는 1 이상 200,000 이하입니다.
  stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
• k는 1 이상 stones의 길이 이하인 자연수입니다.

입출력 예시

stones	k	result
[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]	3	3

풀이

2019 카카오 개발자 겨울 인턴십에 출제된 문제이다. 효율성과 정확성을 둘 다 체크하는 문제라고 명시되어 있다. 따라서 일반적인 접근 방법으로는 시간초과가 날 것을 예상할 수 있다. 시간 최적화가 가능한 여러 기법 중에 하나를 골라 풀이를 해야한다. 어떤 방법으로 문제를 풀어갈 지 다음 과정에서 차례차례 살펴보자.

건너뛸 수 있는 돌의 개수

메인 함수에 전달되는 k값은 니니즈 친구들이 건너뛸 수 있는 최대값이다. 이때 건너뛰는 돌의 개수에 약간 주의를 해야하는데 만약 k값이 3으로 주어진다면, 3개의 돌이 모두 0일때 이를 건너뛸 수 없다. 왜냐하면 3개의 돌을 건너뛰어 도착하는 돌은 출발점으로부터 4칸 떨어진 돌로 인식하기 때문이다. 따라서 자신의 숫자가 0인 돌의 개수가 k개가 되면 건너뛸 수 없다는 것을 알 수 있다.

하나씩 차례로 접근?

가장 단순하게 푸는 법은 이중 반복문을 통해, 니니즈 친구가 한 명씩 지나갈 때 마다 돌의 값을 1식 빼주고, 0이 되는 돌의 개수를 체크하여 연속된 돌의 개수가 k가 될 때를 체크하는 방법이 있다. 그러나 이 경우 stones의 길의가 최대 20만이고, 각 원소의 최대값은 2억이 되므로 당연히 시간초과가 나게 될 것이다. 따라서 우리는 시간복잡도를 최적화 할 수 있는 다른 방법으로 접근이 필요하다.

최대값 OR 최소값

따라서 접근 방식을 다르게 해보자. stones 배열의 각 원소들의 값은 최소 1 이상, 최대 2억 이하가 된다. 즉 이말은 징검다리를 건널 수 있는 최소 인원 result의 값이 최소 1이상, 최대 2억이라는 말과도 같다. 모든 돌의 값이 1이라면 단 한명만 징검다리를 건너갈 수 있고, 모든 돌의 값이 2억이라면 2억명의 니니즈 친구들이 돌을 건너갈 수 있기 때문이다. 최소값과 최대값이 정해져있고, 이 사이에서 문제에서 요구하는 적정값을 찾아야 하는 상황이 되었다. 이 상황에서 자연스레 이분탐색을 활용해야 하겠다는 생각이 들 수 있다. 이분탐색의 시간복잡도는 O(logN)이므로 시간 복잡도 역시 큰 문제가 되지 않음을 예측할 수 있다.

이분탐색

따라서 이분탐색을 이용하여 건너갈 수 있는 니니즈 친구들의 최대값을 찾아주도록 하자. 위와 같이 min, max 로 접근해도 되고 left, right 의 개념으로도 접근할 수 있다. 이때까지 left, right 키워드로 이분탐색을 많이 구현했기 때문에 여기서도 동일한 키워드를 사용하도록 하겠다. 따라서 초기 left 값은 1, right 값은 2억이 될 것 이다.

mid 값은 당연히 (left + right) / 2 값이 될 것이다. 이때 소수점 이하는 버려주도록 하자. 계산된 mid 값은 건너갈 수 있는 최대 니니즈 친구들을 의미한다. 해당 친구들이 모두 돌을 건너가기 위해서는 0이 되는 돌이 k번 연속되지 않아야 한다. 따라서 mid 값을 stones 배열의 각 원소에서 빼주도록 하자. 빼고 난 뒤의 결과값이 0보다 작거나 같은 경우가 k 번 연속되는 경우에 해당 mid 값은 정답이 될 수 없다.

만약 0이 되는 돌이 k번 연속되는 경우라면 최대값의 범위를 mid 값 보다 작게 설정하여 다시 이분탐색을 적용해야 한다. 따라서 right 값을 mid - 1 하여 다시 이분탐색을 진행하도록 하자. 만약 k번 보다 돌의 개수가 작은 경우는 더 많은 니니즈 친구들이 징검다리를 건너갈 수 있는 상황이다. 따라서 최소값의 범위를 mid 값 보다 크게 설정하여 이분 탐색을 적용해야 하므로 left = mid + 1 하고 다시 탐색을 진행하도록 하자.

이를 left가 right 보다 작거나 같을때까진 이분탐색을 반복하도록 해주자. left가 right 와 같은 값이 되었을때도 니니즈 친구들의 최대 인원을 구해주어야 하기 때문이다. 이때 정답으로 리턴해주어야 하는 값은 left 임에 주의하자! right 값은 계속 큰 값에서 작은 값으로 줄어드는 값이고, left 값은 작은 값에서 큰 값으로 상승하기 때문에 left 변수에 건널 수 있는 최대 인원이 담기게 된다.

// 최소값과 최대값 범위 설정
let left = 1;
let right = 2000000000;

// 반복은 left 값이 right 값을 초과하기 전까지 수행
// 둘의 값이 같아지는 경우에도 검사해야 하기 때문
while(left <= right) {
  const mid = (left + right) / 2 >> 0;
  // 원소값에 min 값을 빼줄 것이기 때문에
  // 원본배열의 값을 유지하기 위해 복제하여 진행
  const copy = stones.slice();
  // 반복문 탈출 플래그와
  // 연속되는 0의 돌 개수를 저장할 count
  let flag = false;
  let count = 0;
  
  // 각 원소에 현재 인원(= mid)값을 빼주고
  for(let i = 0; i < copy.length(); i++)
    copy[i] -= mid;
  
  // 빼준 값을 가지고 반복문을 돌면서
  for(const value of copy) {
    // 0보다 작거나 같은 값이 있을 때 기존 count += 1
    // 만약 중간에 0보다 큰 값이 있으면 연속나열이 깨지므로
    // 다시 값을 0으로 초기화
    count = value <= 0 ? count+1 : 0;
    
    // 따라서 count가 k와 동일해지는 순간은
    // k개 만큼 연속되는 0의 돌이 발생하는 순간
    if(count === k) {
      // 플래그를 세워주고 반복문 탈출
      flag = true;
      break;
    }
  }
  
  // 플래그가 세워진 경우는 현재 mid 값이 너무 크기때문에
  // 최대값의 범위를 현재 mid 값으로 줄이고
  // 반대의 경우는 현재 mid 값이 너무 작은 경우이므로
  // 최소값의 범위를 현재 mid 값으로 늘리며
  // 이분탐색을 계속 진행
  flag ? right = mid-1 : left = mid+1;
}

// 따라서 최대값은 left에 저장되게 된다
return left;

전체코드

이분탐색으로 접근해야 한다는 점을 캐치할 수 있었다면 굉장히 쉽게 풀 수 있는 문제였던 것 같다. 기존 이분탐색을 구현하는 것 외에 크게 따로 구현해주어야 할 부분이 없었기 때문이다. 하지만 이분탐색으로 접근해야겠다라는 생각을 떠올리지 못했다면 효율성을 통과하기 위해 꽤나 애를 먹었을 수도 있다. 다음은 주석을 제외한 전체코드이다.

function solution (stones, k) {
  let left = 1;
  let right = 200000000;
  
  while(left <= right) {
    const mid = (left + right) / 2 >> 0;
    const copy = stones.slice();
    let flag = false;
    let count = 0;
    
    for(let i = 0; i < copy.length; i++)
      copy[i] -= mid;
    
    for(const value of copy) {
      count = value <= 0 ? count+1 : 0;
      
      if(count === k) {
        flag = true;
        break;
      }
    }
    
    flag ? right = mid - 1 : left = mid + 1;
  }
  
  return left;
}

출처

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