[프로그래머스/Level3] 징검다리 건너기 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 이분 탐색 ▷ 대상 : 징검다리 건널 수 있는 친구들 수

1. 탐색하는 친구가 건널 수 있다면, 중간 값보다 작은 값들로 모두 건널 수 있음을 의미한다. 그러면 그 때 중간 값보다 많은 인원으로 건널 수 있는지 확인한다.

2. 탐색하는 친구가 건널 수 없다면, 중간 값보다 큰 수로는 건널 수 없음을 의미하므로, 중간 값보다 적은 인원으로 건널 수 있는지 확인한다.

 

 

 

🔺 코드

class Solution {
    static int[] stones;
    static int k;
 
    public int solution(int[] stones, int k) {
        this.stones = stones;
        this.k = k;
 
        int answer = 0;
 
        int left = 1;
        int right = Integer.MAX_VALUE;
        
        while (left <= right) { // 💥 이분탐색 대상 : 징검다리 건널 수 있는 친구 수
            int mid = (left + right) / 2;
 
            if (canCross(mid)) { // 다리 건널 수 있으면, 더 많은 친구들이 가능한지 친구 수 넓히기
                left = mid + 1;
                answer = Math.max(answer, mid);
            } else { // 다리 건널 수 없으면, 친구 수 좁히기
                right = mid - 1;
            }
        }
 
        return answer;
    }
 
    // 징검다리 건널 수 있는지 확인하는 메서드
    private static boolean canCross(int num) {
        int count = 0; // 연속으로 0이 되는 횟수
        
        for (int stone : stones) {
            if (stone - num < 0) { // 디딤돌 숫자 - 건너는 친구 수
                count++;
                if (count >= k) { // 최대칸 수 넘으면 건널 수 없음
                    return false;
                }
            } else {
                count = 0;
            }
        }
 
        return true;
    }
}
 

 

 

 

➕ 다른 풀이 방식

- 이분 탐색 대상이 "지점 간 최소 거리"인 풀이. 돌을 하나씩 지우면서 진행한다. (+친절한 그림 설명들)

[프로그래머스] 징검다리 (Java)

 

[프로그래머스] 징검다리-JAVA

---

💦 어려웠던 점

- 이분 탐색 대상을 잘 잡고 가면 풀 수 있을 것 같다..  이분 탐색 문제를 더 풀어봐야겠다..

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

[프로그래머스/640464] 징검다리 건너기 (Java)

 

[프로그래머스]징검다리 건너기 - JAVA

 

 

✔ 유사한 이분탐색 문제

2805번: 나무 자르기

 

1654번: 랜선 자르기

 

2110번: 공유기 설치