[Programmers] 2019 카카오 개발자 겨울 인턴십 - 징검다리 건너기

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

 

 

문제 풀이:

건널 수 있는 "니니지 친구들"의 수를 binary search를 이용하여 구한다.

binary search로 건널 사람의 수를 먼저 정한 후, 징검다리를 스캔하면서 (현재 징검다리 수 - 건넌 사람 수)가 0 미만인 연속된 징검다리의 수가 k개 이상이면 건널 사람 수를 줄이는 식으로 구현하면 된다.

 

* 마지막 사람이 지난 후, 징검다리 숫자가 줄어드는 것이기 때문에, 지금 막 0이 된 경우는 건널 수 있는 것으로 판단한다.

 

소스 코드:

int solution(vector<int> stones, int k) {
	int answer = 0;

	int l = 0,r=200000000;

	while (l <= r) {
		int mid = (l + r) >> 1;

		int cnt = 0;
		for (int i = 0; i < stones.size(); i++) {
			if (stones[i] - mid < 0) {
				cnt++;
				if (cnt >= k) {
					r = mid - 1;
					break;
				}
			}
			else cnt = 0;
		}
		if (cnt<k) {
			answer = max(answer, mid);
			l = mid + 1;
		}
	}
	return answer;
}