[Programmers] 징검다리 건너기

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/64062

프로그래머스

이분 탐색을 이용하는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. stones 배열의 각 원소의 값이 최소 1이므로 left를 1, right를 stones 배열 내 최고 원소로 선언합니다.

2. 1번에서 구한 left와 right를 기준으로 이분 탐색을 진행하여 mid를 기준으로 조건을 성립하는지 확인합니다.

2.1 조건을 성립하면 answer를 업데이트하고 mid를 높여야하므로 left를 mid + 1로 저장합니다.

2.2 조건을 성립하지 않으면 mid를 줄여야하므로 right를 mid - 1로 저장합니다.

3. 2번에서 구한 answer를 반환합니다.

 

	#include <string>
	#include <vector>
	#include <algorithm>
	#include <queue>
	#include <iostream>
	using namespace std;
	bool canCross(int mid, vector<int> stones, int k)
	{
	queue<int> q;
	for (int i = 0; i < stones.size(); i++)
	{
	stones[i] = max(stones[i] - mid + 1, 0);
	if (stones[i])
	{
	q.push(i + 1);
	}
	}
	int prevIdx = 0;
	int maxDistance = 0;
	while (!q.empty())
	{
	int curIdx = q.front();
	q.pop();
	maxDistance = max(maxDistance, curIdx - prevIdx);
	prevIdx = curIdx;
	}
	int stonesSize = stones.size();
	maxDistance = max(maxDistance, stonesSize - prevIdx + 1);
	return maxDistance <= k;
	}
	int solution(vector<int> stones, int k) {
	int maxStone = 0;
	for (int stone : stones)
	{
	maxStone = max(maxStone, stone);
	}
	int left = 1, right = maxStone;
	int answer = 0;
	while (left <= right)
	{
	int mid = (left + right) / 2;
	if (canCross(mid, stones, k))
	{
	answer = max(answer, mid);
	left = mid + 1;
	}
	else
	{
	right = mid - 1;
	}
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~