22.05.22. 풀었던 문제들

1. 징검다리 건너기

제일 처음 접근은 '어떤 index i부터 i+k-1까지 max값들 중 min값이 답이다'였는데, 이렇게 풀면 답은 맞지만 O(n * (n-k))이므로 O(n^2)이고, n은 max 20만이므로 시간초과가 난다.

int solution(vector<int> stones, int k) {
    int answer = 0;
    int size = stones.size();
    int min_value = 2100000000;
    for(int i = 0; i<=size-k; i++){
        int max_value = stones[i];
        for(int j = i+1; j<=i+k-1; j++){
            max_value = max(max_value, stones[j]);
        }
        min_value = min(min_value, max_value);
    }
    
    
    return min_value;
}

 

다른 방법으로 풀어야 한다. 배열 크기는 20만으로 작은 편이지만 각 원소의 값이 20억 이하다. -> 원소의 값은 크지만 배열 크기는 작다 -> 이분 탐색으로 풀 수 있다 가 떠오른다. 계산해 보면 32 * 20만 -> 640만이므로 시간 내에 풀 수 있을 것이라 예측된다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool isPassable(int num, vector<int>& stones, int k){
    int cnt = 0;
    for(int i = 0; i<stones.size(); i++){
        if(stones[i] - num <= 0) cnt++;
        else cnt = 0;
        if(cnt >= k) return false;
    }
    return true;
}

int solution(vector<int> stones, int k) {
    int answer = 0;
    int size = stones.size();
    
    int l = 1, r = 200000000, mid;
    
    // binary search lower bound
    while(l < r){
        mid = (l+r)/2;
        if(!isPassable(mid, stones, k)) r = mid;
        else l = mid+1;
    }
    return r;
}

/*

어떤 idx i에 대해
i+1, i+2, ... , i+k-1이 모두 i보다 작거나 같다면
i, i+1, ... , i+k-1 중 max값이 그것임.

*/