[프로그래머스] 징검다리 건너기 / 2019 카카오 개발자 겨울 인턴십 - JAVA

🖇️ 문제 링크

코딩테스트 연습 - 징검다리 건너기

카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리 가 있는 개울을 만나서 건너편으로 건너려고 합니다. "라이언" 선생님은 "니니즈 친구들"이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다. 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.

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

 

---

📝 문제 분석

💡

isMove(n, k, stones) = n명의 사람이 징검다리를 건널 수 있는가?

n보다 작은 징검다리가 k번 연속 나온다면 그 다음 사람은 징검다리를 건널 수 없습니다.

이를 만족하는 최대의 n을 구하기 위해서 이분탐색 최적화 결정문제로 해결했습니다.

 

---

⌨️ 코드

class Solution {
    public int solution(int[] stones, int k) {
        int ans = 0;
        int lo = 0, hi = Integer.MAX_VALUE;
        while(lo <= hi) {
           	int mid = (lo + hi) / 2;
            
            if(isMove(mid, k, stones))
               	lo = mid + 1;
            else
                hi = mid - 1;
        }
        return lo - 1;
    }
    
    public boolean isMove(int n, int k, int[] stones) {
        int cnt = 0;
       	for(int stone : stones) {
           	if(stone < n)
                cnt++;
            else
                cnt = 0;
            if(cnt == k)
                return false;
        } 
        return true;
    }
}

 

 

 

 

Uploaded by Notion2Tistory v1.1.0