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

Question

• 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/64064
• 분류 : 이진탐색
• 풀이 시간 : 60분

문제 해설

1. 징검다리 디딤돌 존재 + 각 디딤돌에는 값이 부여되어있음
2. 친구들은 징검다리를 건너서 가야 함
3. 징검다리를 건너기 위해 디딤돌을 밟으면 디딤돌의 수가 1씩 줄어듬
4. 디딤돌을 밟을 때 가장 가까운 디딤돌로만 뛸 수 있음
   1. 최대 k개까지 건너뛸 수 있음
5. 징검다리를 건너는 친구들의 최대 수는?

Solution

풀이 접근 방법

1. 효율성까지 보는 문제이기 때문에 대부분 이진탐색이나 dp 등등....
2. 이진탐색할 것 = 징검다리를 건널 수 있는 친구들의 수
   1. 탐색하는 친구의 수가 건널 수 있음 = true = 중간 값보다 작은 값들로는 모두 건널 수 있음을 의미 => 중간 값보다 큰 인원으로 건널 수 있는지 확인
   2. 탐색하는 친구의 수가 건널 수 없음 = false = 중간 값보다 큰 수로는 모두 건널 수 없음을 의미 => 중간 값보다 적은 인원으로 건널 수 있는지 확인

정답 코드

class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;
      	// 징검다리를 건너는 친구의 최소 수
        int min = 1; 
        // 징검다리를 건너는 친구의 최대 수
        int max = 200000000;
	      
        // 이분탐색 할 기준 : 징검다리는 건널 수 있는 친구의 수
        while (min <= max) {
          	// 징검다리를 건널 인원
            int mid = (min + max) / 2;
            
            // 징검다리 건널 수 있는지 확인
            if (canAcrossRiver(stones, k, mid)) {
              	// 다리를 건널 수 있으면 더 많은 친구들이 가능한지 친구의 수를 넓힘
                min = mid + 1;
                answer = Math.max(answer, mid);
            } else {
                // 다리를 건널 수 없으면 친구의 수를 좁힘
                max = mid - 1;
            }
        }
        
        return answer;
    }
    
    boolean canAcrossRiver(int[] stones, int k, int friends) {
        // 못 건너는 징검다리의 개수를 저장
      	int skip = 0;
        
        for (int stone : stones) {
            // 디딤돌의 숫자 - 건너는 친구의 수
            if (stone - friends < 0)
              	// 0보다 작으면 건널 수 없음을 의미
                skip++;
            else
              	// 0 이상이면 건널 수 있음의 의미 = 이 지점에 위치하면 다음으로 갈 수 있음
                // 다시 0으로 갱신
                skip = 0;
            
            // 못 건너는 징검다리의 수가 최대칸 k를 넘으면 해당 값은 건널 수 없음을 의히
            if (skip == k)
                return false;
        }
        
        return true;
    }
}