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

문제

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

프로그래머스

 

---

문제 개요

카카오 초등학교의 "니니즈 친구들"이 징검다리를 건너려고 합니다. 징검다리는 숫자가 적힌 디딤돌들로 이루어져 있고, 디딤돌은 밟을 때마다 숫자가 1씩 줄어듭니다. 숫자가 0이 되면 해당 디딤돌은 더 이상 밟을 수 없으며, 친구들은 건너뛸 수 있지만 최대 k칸까지만 건너뛸 수 있습니다. 이때, 최대 몇 명의 친구들이 징검다리를 건널 수 있는지 구하는 문제입니다.

접근 방법

1. 이진 탐색을 사용하여 건널 수 있는 최대 인원을 구합니다.
   • 한 번에 몇 명이 건널 수 있는지 min과 max 범위를 설정한 후, 이 범위 내에서 가능한 인원수를 이분 탐색으로 찾습니다.
   • mid 값을 사용하여 그 인원만큼 징검다리를 건널 수 있는지 여부를 확인합니다.
2. 조건을 확인하는 방법:
   • mid만큼의 인원이 징검다리를 건널 수 있는지 확인할 때, mid보다 작은 값의 디딤돌이 연속으로 k개 있는지를 확인합니다. 만약 그런 상황이 발생하면 그 인원은 건널 수 없으므로 불가능하다고 판단합니다.

해결 과정

1. 이진 탐색을 이용한 인원수 계산:
   • 초기 범위를 min = 0부터 max = 200,000,000으로 설정한 후, 이 범위 내에서 가능한 최대 인원을 찾습니다.
   • 중간값 mid에 대해 그 인원이 징검다리를 건널 수 있는지 확인하고, 가능하다면 더 큰 인원을 탐색합니다. 불가능하다면 더 작은 범위로 줄여 나갑니다.
2. 건너뛸 수 있는지 여부 확인:
   • check 함수는 mid명이 건널 수 있는지를 판단합니다. 각 디딤돌을 하나씩 확인하며, mid보다 작은 디딤돌을 만날 때마다 카운트를 증가시킵니다.
   • 연속해서 k개 이상의 디딤돌을 밟을 수 없으면 그 인원은 건너는 것이 불가능하다고 판단하여 false를 반환합니다.

주요 포인트

1. 이진 탐색을 통한 효율성:
   • 탐색 범위를 절반씩 줄여가며 가능한 최대 인원을 찾는 방식은 시간 복잡도를 O(log(max) * n)으로 줄여줍니다. 이때 n은 징검다리의 길이이고, max는 최대 인원수인 200,000,000입니다.
   • 이진 탐색 관련 글 
2. 연속된 건널 수 없는 디딤돌의 처리:
   • k칸을 넘어서면 더 이상 건널 수 없다는 조건을 정확하게 반영하여 디딤돌을 밟을 수 있는지 체크하는 과정이 핵심입니다.

 

import java.util.*;
class Solution {    
    public int solution(int[] stones, int k) {
        int answer = 0;
        int max = 200_000_000;
        int min = 0;
        
        while(min <= max) {
            int mid = (max+min)/2;
            if(check(mid, stones, k)) {
                answer = Math.max(answer, mid);
                min = mid+1;
            } else {
                max = mid-1;
            }
        }
        return answer;
    }
    
    public boolean check(int mid, int[] stones, int k) {
        int cnt = 0;
        for(int i=0; i<stones.length; i++) {
            if(stones[i] < mid) cnt++;
            else cnt = 0;
            if(cnt == k) return false;
        }
        return true;
    }
}