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

✔️ 문제

• 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/64062
• 2019 카카오 개발자 겨울 인턴 코딩 테스트 기출문제

✔️ 풀이

• 징검다리를 건널 수 있는 니니즈 친구들의 최대 수를 찾아야 한다.
• 문제에서 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한이라고 간주하는데, 징검 다리를 건널 수 있는 니니즈의 수는 최대 200,000,000 마리다. (모든 디딤돌의 숫자가 200,000,000라고 가정해보면 최대 200,000,000마리 건널 수 있다.)
• 최대 몇 마리가 건널 수 있는지 0마리부터 200,000,000마리까지 다 확인하면 되는데, 이 경우 시간이 너무 오래걸린다. (시간 복잡도 = 200,000,000 x n마리가 건널 수 있는지 검사하는 로직)
• 따라서 최대 니니즈 마리수는 이분탐색으로 찾아야 한다.
• 매번 니니즈들이 징검 다리를 건너고 난 상황을 시뮬레이션하고, 숫자가 0인 징검다리의 연속됨이 k개 이상인지 확인하며, 아래와 같이 이분탐색 한다.
  • k개 이상이라면, 징검 다리를 건너는 니니즈 수를 감소시켜본다.
  • k개 이하라면, 징검 다리를 건너는 니니즈 수를 증가시켜본다.

👨🏻‍💻 소스 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int solution(vector<int> stones, int k) {
	int low = 0, high = 200000000;

	while (low <= high) {
		int mid = (low + high) / 2;
		vector<int> tmpStones = stones;

		for (int i = 0; i < tmpStones.size(); i++) {
			if (tmpStones[i] - mid <= 0)
				tmpStones[i] = 0;
		}

		int cnt = 0;
		bool flag = true;

		for (int i = 0; i < tmpStones.size(); i++) {
			if (tmpStones[i] == 0)
				cnt++;
			else
				cnt = 0;

			if (cnt >= k) {
				flag = false;
				break;
			}
		}

		if (flag) { // 니니즈 수를 증가 시켜본다.
			low = mid + 1;
		}
		else { // 니니즈 수를 감소 시켜본다.
			high = mid - 1;
		}
	}

	return low;
}

✔️ 문제 회고

• 구하고자 하는 답의 범위를 보며, 이분 탐색 문제라는 것을 파악할 수 있어야 풀 수 있는 문제다.