주요 개념
이분 탐색, 시뮬레이션
문제 포인트
1) 징검다리의 돌을 밟아 반대편으로 건너가려고 한다.
2) 위 그림처럼 각 돌에 숫자가 있고 한번 밟을 때마다 숫자가 줄어든다.
3) 돌의 수가 0이 되면 밟을 수 없고 건너뛰어야 한다.
4) 최대로 건너 뛸 수 있는 숫자 k가 주어질 때 최대 몇명이 징검다리를 건널 수 있는지 구해라.
k가 3일 때 위 그림에서 네 번 건너뛰어야 하기 때문에 불가하다.
문제 해결 과정
stones 배열의 크기는 1 이상 200,000 이하입니다.
stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
k는 1 이상 stones의 길이 이하인 자연수입니다.
이러한 조건을 보면 분명 이중 for문을 사용하면 절대 안된다. 그리고 문제의 핵심은
"n번째 사람이 건널 수 있는 조건은 n-1번까지 사람이 다 건넜을 때 0인 돌이 연속으로 k개 미만이어야 한다(이상인 순간 못건넘)"이다.
단순히 시뮬레이션으로 생각한다면, stones 배열의 원소를 순회하면서 1씩 줄이고 연속된 0을 찾는 것인데, 원소들의 값이 2억 이상이기 때문에 산술적으로 불가능하다.
나의 생각
그래서 처음 생각한 것은 stones 배열의 원소를 k개로 묶은 후 가장 큰 수가 그 묶음이 연속으로 0이 되는 수라고 정의하고 k개로 묶음을 돌면서 가장 큰 수를 찾았고, 그중에 가장 작은 수가 정답이라고 생각했다(가장 먼저 연속된 0이 k개가 되는 묶음).
이것은 O(nk)인데... 역시나 시간에서 걸렸다..
이 이상 다른 것은 생각하지 못했고 해설을 보고 해결했다.
이분 탐색
이분 탐색(Binary Search)
정렬된 배열에서 O(logn) 으로 원소를 찾는 방법
"이분 탐색"이라 함은 정렬된 원소에서 하나 찾아내는 방법으로만 틀에 박혀있어서 전혀 생각하지 못했는데, "1~원소중에 가장 큰 값" 으로 이분 탐색을 진행하는 것이다.
이러한 문제가 분명히 있었는데 적용하지 못했다. 아마 이런 뉘앙스 문제였다.
N개의 은행 창구가 있고 각자 일처리 속도가 다르다. 일처리 속도를 담은 배열과 총 시간이 주어졌을 때 최대한 처리할 수 있는 고객의 수?
이 문제를 처음 풀때 큐, 우선순위큐 별걸 다 써봤는데..
그냥 이분탐색이었다.
아래 코드를 보면 이해할 수 있다.
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool isPossible(vector<int>& stones, int& k, int& mid){
int cnt=0;
for(int i = 0; i<stones.size(); i++){
if(stones[i]-mid+1<=0){
if(++cnt>=k) return false;
}else{
cnt = 0;
}
}
return true;
}
int solution(vector<int> stones, int k) {
int left = 1;
int right = *max_element(stones.begin(), stones.end());
int mid;
int answer = 1;
while(left<=right){
mid = (left+right)/2;
if(isPossible(stones, k, mid)){ //가능하면 높은 수로 해보기
cout<<mid<<"가능"<<endl;
answer = mid;
left = mid+1;
}else{ //불가능하면 낮은 수로 해보기
cout<<mid<<"불가능"<<endl;
right = mid-1;
}
}
return answer;
}주의해야할 점
분명히 정답이랑 비슷(?)한데 계속 틀리다고 나와서 뭐가 다른지 계속 본 결과..
나의 코드는 mid를 정하면 각 원소를 mid만큼 빼고 연속된 0이 k개 있으면 불가능한 것으로 판별했는데, 틀렸다.
mid-1명이 밟고 지나갔을 때 mid번째 사람이 연속된 k개의 0이 있으면 못건너는 것이었다.
배운 내용
이런 Edge Case 처리 잘하기.
이런 비슷한 유형에서 이분 탐색 적용하기.
