⚙️ 알고리즘 분류 : 이분 탐색
🔠 언어 : c++
🤫 힌트.
숫자들 중 그 사이 어딘가를 맞춰야 하는 느낌.
그리고 배열의 크기가 매우 크다! 무조건 linear 하게 해야 한다.
✏️ 풀이.
직감이 왔다. 딱 봐도 이분 탐색 문제.
징검다리에 적힌 숫자를 중복 없이 모아서 정렬한다. set으로 구현했다.
그리고 이분 탐색의 start, end를 0, (전체 숫자 개수)-1. 즉, index로 설정했다.
건널 수 없는 돌다리가 나오면 임의의 변수에 값을 1씩 더하다가,
한 번이라도 건널 수 있는 돌다리면 바로 0으로 바꿨다.
그리고 1씩 더하다가 한 번에 점프할 수 있는 값(k) 이상이면 틀린 답이므로 바로 멈췄다.
임의의 변수가 k 이상이면 end를 줄이고,
k 미만이면 start를 늘림과 동시에 답이 될 수 있는 경우이므로 mid index의 값을 저장했다.
⚠️ 헤맨 부분.
돌에 적힌 숫자를 a, 지나가는 사람의 수를 b라고 가정.
a<=b 라면, 돌다리를 건널 수 없는 상태라고 했다.
근데 그렇게 되니까 실제 답보다 1 작은 수가 나와서 문제를 다시 읽어보니,
건너고 나서 숫자가 사라지는 거였다. 그래서 등호=를 뺐더니 됐다.
👩🏻💻 코드.
#include <string>
#include <vector>
#include <set>
#include <iostream>
using namespace std;
set<int> s;
vector<int> v;
int solution(vector<int> stones, int k) {
int answer = 0;
// 징검다리 숫자를 중복없이 정렬해서 모은다.
for(int i=0; i<stones.size(); i++) s.insert(stones[i]);
for(auto it=s.begin(); it!=s.end(); it++) v.push_back(*it);
int start=0, end=v.size()-1;
// 이분 탐색 Let's go!
while(start<=end){
// cont는 연속적으로 돌 숫자가 0 이하인 상태의 횟수.
int mid=(start+end)/2, cont=0;
for(int i=0; i<stones.size(); i++){
// 건너갈 수 없는 상태
if(stones[i]<v[mid]){
cont++;
// 만약 한 번에 점프할 수 없다면
// 이미 해당 mid는 탈락이므로 멈춘다.
if(cont>=k) break;
}
else cont=0;
}
// 한 번에 점프할 수 없는 case.
// 징검다리에 더 적은 사람이 건너가야 한다.
if(cont>=k) end=mid-1;
else{
// 답이 될 수 있는 case
start=mid+1;
answer=max(answer, v[mid]);
}
}
return answer;
}😎 후기.
예전에 이 문제를 풀었을 땐, 못 풀어서 답을 봤는데... 다시 풀 땐 나 혼자서 맞췄다! 참내~ 이걸 왜 못푼겨~ 과거의 나
파닥파닥