[프로그래머스 / Lv.3] - 징검다리 건너기 (Java)

문제

---

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

프로그래머스

 

---

문제 풀이

---

이 문제는 이진 탐색(Binary Search)와 투 포인터(Two Pointer) 기법을 사용하여 해결할 수 있다. 

 

배열의 크기가 최대 200,000,000 이므로 순차탐색의 경우 효율성이 떨어진다.

 

1. 이진 탐색을 사용하여 최대 인원을 찾기

• 가능한 최소 인원은 1명, 최대 인원은 200,000,000명으로 설정하고 이진 탐색을 시작한다.
• 중간값을 계산하고, 이 인원이 징검다리를 건널 수 있는지를 확인한다.
• 건널 수 있다면, 더 많은 인원이 건널 수 있는지 확인하기 위해 범위를 늘리고, 건널 수 없다면 범위를 줄인다.
  
  • 각 디딤돌을 순회하며, 현재 인원이 건널 수 있는지 확인한다.
  • 연속으로 건널 수 없는 디딤돌의 수가 k를 초과하면 건널 수 없다고 판단한다.
    
    

코드 구현

class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;
        int left = 0, right = 200_000_000;
        
        while(left <= right) {
            int mid = (left + right) / 2;
            
            if(canCross(stones, k, mid)) {
                answer = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return answer;
    }
    
    private boolean canCross(int[] stones, int k, int mid) {
        int count = 0;
        
        for(int stone : stones) {
            if(stone - mid < 0) {
                count++;
                
                if(count >= k) {
                    return false;
                }
            } else {
                count = 0;
            }
        }
        
        return true;
    }
}

 

코드 설명

1. 이진 탐색 초기화

• `left`는 0명, `right`는 최대 200,000,000명으로 설정한다.
  
  

2. 이진 탐색 루프

• `mid` 값을 계산하고, `canCross` 함수를 통해 해당 인원이 징검다리를 건널 수 있는지 확인한다.
• 건널 수 있다면, `answer`를 업데이트하고 `left`를 증가시켜 더 많은 인원을 탐색한다.
• 건널 수 없다면, `right`를 감소시켜 인원을 줄인다.

 

3. 디딤돌 건너기 확인

• `canCross` 함수는 디딤돌 배열을 순회하며, 현재 인원이 건널 수 있는지 확인한다.
• 연속으로 건널 수 없는 디딤돌의 수가 \( k \) 이상이면 건널 수 없다고 판단한다.
• 모든 디딤돌을 순회한 후, 건널 수 있으면 `true`, 아니면 `false`를 반환한다.

 

이와 같이 이진 탐색과 투 포인터 기법을 사용하여 문제를 효율적으로 해결할 수 있다.