[프로그래머스] 징검다리 건너기 with JS

알고리즘 스프린트 10일차 - [프로그래머스] Lv 3. 징검다리 건너기

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

프로그래머스

소요시간

1시간 20분 고민했지만 풀이 실패.. 

 

계획

무지성 DP로 하다가 실패하고 DFS도 실패하고..

징검 다리 문제만 보면 DP가 떠올라서 습관적으로 DP로 접근했는데, 범위가 20만 제곱인 걸 간과했다.

DFS도 뭐 될리가 없지만 풀이가 떠오르지 않아서 DFS 백트래킹으로 해봤지만 어림도 없었다

 

풀이

나의 풀이는 아니지만 chatGPT에게 물어보니 이분 탐색을 활용하면 된다고 하더라..

왜 처음부터 이분탐색을 떠올리지 못했을까 너무 아쉬웠다.

징검다리를 건너는 것에 초점을 두고 있었는데 초점을 조금 바꿔보면 돌의 적힌 수가 결국 건널 수 있는 사람의 수이다.

그럼 돌의 적힐 수 있는 숫자는 범위가 어떻게 될까?

- 최대 2억까지라고 한다.

전체 탐색하면 O(N).. 2억개는 시간초과

그럼 정렬된 선형 구조에서 유용한 이분 탐색을 사용하면

O(logN)으로 처리가 가능하다.

그럼 이 문제에서 돌다리의 길이 M은 최대 20만까지니까

O(MlogN)으로 풀이가 가능하다

 

이분탐색을 활용하여

각 숫자 별로 건널 수 있는지 확인하면서 가장 큰 숫자를 찾아가는 방법으로 접근하니 풀렸다

 

결과

내가 푼 문제는 아니라서 결과를 캡처하진 않겠다.

코드

function solution(stones, k) {
    let left = 0; // 가능한 최소 인원 수
    let right = 200000000; // 가능한 최대 인원 수
    while (left <= right) {
        const mid = Math.floor((left + right) / 2); // 중간 인원 수
        let cnt = 0; // 건널 수 있는 디딤돌의 수
        for (let i = 0; i < stones.length; i++) {
          // mid명이 건널 때, 연속으로 0이되는 돌의 개수를 찾는다.
          if (stones[i] < mid) {
            cnt++;
            if (cnt >= k) break;
          } else {
            cnt = 0;
          }
    }
    // 건널 수 없는 경우, 최대 인원 수를 줄인다.
    if (cnt >= k) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return right; // 가능한 최소 인원 수를 반환
}

마치며

LV 3로 오니까 확실히 문제 접근 자체가 쉽지 않다. 그렇다고 몰랐던 자료구조도 아니고, 접근을 잘못해서 못푸니까 더 화가났다. 앞으로 계속 LV3에 도전하면서 접근 방법에 익숙해져야할 것 같다.