프로그래머스 - 징검다리 건너기

프로그래머스 - 징검다리 건너기

바이너리서치를 이용했다.
left : 0
right : stones 중 최대 값
으로 초기 설정을 하고, mid 값은 N명의 친구가 건넜을 때이다.

stones 배열에서 mid 값을 빼고, 만약 0이하의 원소가 K개 이상일 경우 해당 mid 값은 불가능한 경우이다. 따라서 이 경우엔 더 작은 mid 값을 찾아야하므로 right를 mid - 1로 설정해주고, 그 외에는 left를 mid + 1로 설정해줘서 더 큰 mid 값(즉, 더 많은 친구가 건널 수 있음)을 찾으면 된다.

코드는 다음과 같다.

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

using namespace std;

int solution(vector<int> stones, int k) {
    int left = 0;
    int right = *max_element(stones.begin(), stones.end());
    while(left <= right) {
        int mid = left + (right - left) / 2;
        int count = 0;
        bool is_okay = true;
        for(int i=0;i<stones.size();i++) {
            int val = stones[i] - mid;
            if(val > 0) 
                count = 0;
            else {
                count++;
                if(count >= k) {
                    is_okay = false;
                    break;
                }
            }
        }
        if(is_okay) 
            left = mid + 1;
        else 
            right = mid - 1;
    }
    
    return left;
}

추가적으로 multiset을 이용한 sliding window 방식의 풀이이다. 초기에 이런 방식으로 구현하다 바이너리서치로 선회해서 풀었는데, 비록 느리긴해도 괜찮은 풀이 방식이다.

핵심은 K개로 이루어진 window의 최댓값 만큼 징검다리를 건널 수 있는 것이고, 그러한 window들의 최댓값들 중 최솟값이 최종 정답이 된다는 것이다.

이 풀이는 O(NlogK)의 시간복잡도고, 위 이분탐색의 풀이는 O(NlogM)의 풀이방식이다.

여기서 M은 원소들의 최댓값을 의미하고,
N은 배열의 크기, K는 배열의 크기 이하의 숫자이므로 배열의 크기인 N과 동일하게 취급해도 된다.

문제에서는 M은 1이상 200,000,000 이하의 자연수이고, N과 K는 1에서 200,000 사이의 숫자인데, 신기하게도 이분탐색이 더 빠르다.
아마 stones 배열에 200,000을 넘는 매우 큰 숫자가 포함된 테스트케이스가 없는 것 같다.

코드는 다음과 같다.

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

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    multiset<int> s;
    
    for(int i=0;i<k;i++) 
        s.insert(stones[i]);
    
    answer = *--s.end();
    
    for(int i=k;i<stones.size();i++) {
        s.insert(stones[i]);
        
        s.erase(s.find(stones[i - k]));
        
        answer = min(answer, *--s.end());
    }
    
    return answer;
}