[프로그래머스] : 징검다리건너기(c++)

[문제] : https://programmers.co.kr/learn/courses/30/lessons/64062

[풀이]

슬라이딩 윈도우와 세그먼트 트리를 활용해 풀었다. k범위의 슬라이딩 윈도우를 적용 하였을 때 범위 내의 모든 디딤돌이 0이 되면 건너 갈 수 없다. 따라서 범위 내의 최대값들 중의 최소값을 찾으면 된다. 이때 구간 내의 최대값을 찾기 위해 반복문을 사용하면 시간초과가 발생하기 때문에 세그먼트 트리를 사용하였다.

[코드]

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

using namespace std;
int rangeMax[800000];

int init(const vector<int>& array, int left, int right, int node)
{
    if (left == right) return rangeMax[node] = array[left];
    int mid = (left + right) / 2;
    int leftMax = init(array, left, mid, node * 2);
    int rightMax = init(array, mid + 1, right, node * 2 + 1);
    return rangeMax[node] = max(leftMax, rightMax);
}

int query(int left, int right, int node, int nodeLeft, int nodeRight)
{
    if (right < nodeLeft || left > nodeRight) { 
        return -1; 
    }

    if (left <= nodeLeft && right >= nodeRight) return rangeMax[node];

    int mid = (nodeLeft + nodeRight) / 2;

    return max(query(left, right, node * 2, nodeLeft, mid), query(left, right, node * 2 + 1, mid + 1, nodeRight));
}
int solution(vector<int> stones, int k) {
    int answer = 210000000;
    init(stones,0,stones.size()-1,1);

    int left = 0;
    int right = k-1;

    while(1)
    {
        if(right >= stones.size()) break;
        int k = query(left,right,1,0,stones.size()-1);
        answer = min(answer,k);
        left++, right++;
    }

    return answer;
}