[Programmers] Lv3. 징검다리 건너기

• 이 글은 c++로 풀이를 작성하였습니다.

문제

예시

---

풀이 1

• O(n)의 풀이 방법

	#include <string>
	#include <vector>
	#include <map>
	#include <algorithm>
	using namespace std;
	// 카카오 정석풀이는 이분탐색이지만 O(nlogn)보다 더 줄이는 방법으로 O(n)이 있다.
	// k개의 윈도우에서 최댓값이 윈도우를 못건너게 되는 값이다. 이 값이 최소가 되는 지점이 바로 정답이 된다.
	int solution(vector<int> stones, int k) {
	int answer = 200000000;
	// 중복된 key도 포함시키기 위한 map
	multimap<int,int> m;
	// multimap의 정렬은 key와 value가 오름차순으로 정렬되어 있다.
	// key가 동일할 경우 index가 작은값부터 확인하기 위해 음수를 취한다.
	for(int i=0;i<k;i++){
	m.insert({stones[i],-i});
	}
	// 0부터 k-1번까지의 배열의 값에서 최댓값
	answer = (*--m.end()).first;
	// 가장 나중에 담은 stones 제거 후 i번째 stones 추가
	// 이후 최댓값
	for(int i=k;i<stones.size();i++){
	m.erase(m.find(stones[i-k]));
	m.insert({stones[i],-i});
	int num = (*--m.end()).first;
	answer = min(answer,num);
	}
	return answer;
	}

view raw Programmers Lv3.stepping stone.cpp hosted with ❤ by GitHub

풀이 2

• O(nlogn)의 풀이 방법

  	#include <string>
  	#include <vector>
  	#include <map>
  	#include <algorithm>
  	using namespace std;
  	int solution(vector<int> stones, int k) {
  	int answer = 0;
  	// 건널 수 있는 사람의 수를 기준으로 이분탐색
  	int s = 1;
  	int e = *max_element(stones.begin(),stones.end());
  	while(s<=e){
  	int mid = (s+e)/2;
  	int len = 0;
  	int sum = 0;
  	// mid보다 작은 수가 얼마나 연속되는지 확인 => len
  	for(int i=0;i<stones.size();i++){
  	if(stones[i]<=mid){
  	sum++;
  	}
  	else{
  	len = max(sum,len);
  	sum = 0;
  	}
  	}
  	len = max(sum,len);
  	// len이 k값보다 크거나 같으면 mid보다는 작은
  	if(len>=k){
  	e = mid-1;
  	}else{
  	s = mid+1;
  	}
  	}
  	answer = s;
  	return answer;
  	}

  view raw Programmers Lv3.stepping stone2.cpp hosted with ❤ by GitHub
• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.