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

풀이

1. stones에서 가장 큰 값을 right로 설정하여 이분탐색 진행
2. mid보다 작은 값이 연속으로 k개 이상 나타날 경우 불가능 => 오른쪽으로 ㄱㄱ (left = mid+1)
   • 반대의 경우 왼쪽으로 => right = mid - 1;

 

비고

• 이분탐색... left right 아 어쩌란 말이냐ㅕ~~~~~ 범위 설정이 세상에서 제일 어렵구요 ㅠㅠ

 

 

package KakaoIntern2019.P64062_징검다리건너기;

public class Solution {

	static int solution(int[] stones, int k) {
		int max = 0;
		for (int i = 0; i < stones.length; i++) {
			max = Math.max(stones[i], max);
		}

		int left = 0;
		int right = max;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (possible(stones, k, mid)) {
				left = mid + 1;
			} else
				right = mid - 1;
		}
		return right;
	}

	private static boolean possible(int[] stones, int k, int mid) {
		int cnt = 0;
		for (int i = 0; i < stones.length; i++) {
			if (stones[i] < mid) {
				if (++cnt >= k)
					return false;
			} else {
				cnt = 0;
			}

		}
		return true;
	}

	public static void main(String[] args) {
		int[] s = { 2, 4, 5, 3, 2, 1, 4, 2, 5, 1 };
		System.out.println(solution(s, 3));
	}

}