해당문제 바로가기
이번문제는 이분탐색 문제로, 굉장히 카카오에서 잘 만든 문제인거 같다.
문제의 조건을 보자마자 딱 생각해봐야할것이, stones의 배열크기가 200,000이고, stones의 size가 200,000,000이라는것이다.
만약에 배열의 크기가 200,000인데, 모든 돌의 크기가 200,000,000이라면,
for문을 돌려서는 200,000*200,000,000이므로 시간초과가 무조건 날 것이라는 생각을 할 수 있다.
그렇다면, 이 문제를 쫌 보자마자 이분탐색 써야하나? 싶은게 있는데,
일단, 크기가 200,000,000으로 연산횟수로 따지자면, 1억에 1초니까
최소한 O(N)이나 O(logN)으로 해결해야겠다 라는 생각이 든다.
그리고, 문제의 정답이 최대 건널수있는 사람의 숫자인데, 최대, 최소 같이 딱 특정한 값을 찾아서 답해야할때는 이분탐색을 사용하는게 좋다.
그렇다면, 이분탐색인가? 스윽 냄새를 맡으면 이분탐색의 기준을 정해줘야하는데, 이분탐색은 항상 기준이 중요하다.
어디를 left 어디를 right 어디를 mid로 잡을 것인가? 이걸 잘 생각해야하는데 이걸 찾기가 상당히 까다롭다.
문제에서는 돌을 사람이 밟고 지나간다.
즉, 돌의 무게 == 돌을 밟을 수 있는 사람의 수라는 것이다.
앞의 경우처럼 200,000개의 돌을 전부 200,000,000으로 깔아도 200,00,001명은 건널 수가 없다.
고로 stones의 배열에서 가장 작은 무게의 돌을 left 가장 큰 무게의 돌을 right로 잡는다.
문제 예시에서 들어보면
2, 4, 5, 3, 2, 1, 4, 2, 5, 1
left는 1 right는 5임을 알 수 있다. 그럼 mid는 3이다.
돌을 밟을 수 있는 사람의 수가 3이라고 가정을 하면, 돌의 무게가 3보다 작다면 당연히 돌을 밟을 수 없을것이다.
고로, stones에서 3을 전부 빼주면
0 1 2 0 0 0 1 0 2 0 이고, 000이 연속해서 k보다 크게 나왔으므로 false이다.
무게를 줄여야 하므로 right를 mid-1인 2로 줄이면
left 1 right 2 mid가 1이되고
이건 참이니까 left를 한칸늘려서 2,2가된다.
2,2에서 참이니까 left를 1칸늘려서 3,2가 되고 while문 조건에 부합하지 않아 나가게된다.
그리고 left를 반환하면 끝이다.
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int mmax=0;
int mmin=200000000;
void checkmaxmin(vector<int> &stones){
for(int i=0;i<stones.size();i++){
if(mmax<stones[i]) mmax=stones[i];
if(mmin>stones[i]) mmin=stones[i];
}
}
bool possible(int weight,vector<int> & stones,int possiblemax){
int continuity=0;
for(int i=0;i<stones.size();i++){
if(stones[i]-weight<=0){
continuity++;
}else{
continuity=0;
}
if(continuity==possiblemax) return false;
}
return true;
}
int solution(vector<int> stones, int k) {
//최소,최대 돌 무게 구하기
checkmaxmin(stones);
int start=mmin;
int end=mmax;
while(start<=end){
cout<<start<<" "<<end<<"\n";
int middle=(start+end)/2;
//징검다리 끝까지 간다면 무게를 더 달아도 되니까 start를 늘리고, 징검다리 끝까지 못간다면 무게를 줄여야하니까 end를 줄이기
if(possible(middle,stones,k)){
start=middle+1;
}else{
end=middle-1;
}
}
return start;
}