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

프로그래머스 징검다리 건너기 문제 풀이입니다.

징검다리 건너기

2019년 하반기 카카오 인턴 코딩테스트 문제이다.

이 문제를 풀 당시엔 이분탐색이라는 아이디어가 절 대 안떠올랐다.. 나는 참..

이분탐색을 생각하면 간단하게 풀 수 있는 문제이다.

아이디어는 다음과 같다.

1. 입력받는 돌의 최대 숫자와 최소 숫자를 찾는다.
2. 결국 정답은 최대값과 최소값 사이에 존재하기 때문에 그 두값을 가지고 이분탐색을 시작한다.
3. mid 값을 넣었을 때 그 징검다리를 전부 건널 수 있으면 최대값과 mid를 비교해서 최대값을 갱신해준다.

생각해보면 정말 간단한 개념이지만 이게 시험볼때 생각날 수 있도록 좀 더 역량을 쌓아야겠다.

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

bool is_Possible(int mid,vector<int>& stones,int k) {
	int cur = -1; // 위치
	for (int i = 0; i < stones.size(); i++) {
		if (stones[i] - mid >= 0) {
			if (i - cur > k)return false;
			cur = i;
		}
	}
	if (stones.size() - cur > k)return false;
	return true;
}

int solution(vector<int> stones, int k) {
	int answer = 0;
	int left = *min_element(stones.begin(), stones.end());
	int right = *max_element(stones.begin(), stones.end());
	int mid = 0;
	while (left <= right) {
		mid = (left + right) / 2;
		if (is_Possible(mid, stones, k)) {
			answer = max(answer, mid);
			left = mid + 1;
		}
		else right = mid - 1;
	}
	
	return answer;
}

오늘의 교훈

• 기본은 충실히
• 코드는 간결하게!

소스코드

이 외에도 제가 푼 문제들 소스코드는 다음 링크에 있습니다!!! 알고리즘 문제풀이