프로그래머스 Level 3 징검다리 건너기[C++]

1. 문제 풀이

 문제 유형은 슬라이딩 윈도우입니다. 저는 우선순위 큐를 응용하여 풀이하였습니다. {값, 인덱스} 정보를 저장하고 우선순위 큐 루트 노드의 범위의 벗어난 값이 있으면 모두 소거하는 방식으로 진행했습니다. 이렇게 풀이하면 O(N lg N)으로 풀이할 수 있습니다. 다른 O(N lg N) 방법은 세그먼트 트리를 응용하는 방법이 있는데 게시글 작성 후 바로 추가해 보겠습니다.

 

2. 코드

2 - 1. 우선순위 큐, 슬라이딩 윈도우 기법

#include <bits/stdc++.h>

using namespace std;
using pi = pair<int, int>;
#define X first
#define Y second

priority_queue<pi> pq;

int solution(vector<int> s, int k) {
    for(int i = 0; i < k; i++) {
        pq.push({s[i], i});
    }

    int ans = pq.top().X;

    for(int i = k; i < s.size(); i++) {
        while(!pq.empty() && pq.top().Y <= i - k) {
            pq.pop();
        }
        pq.push({s[i], i});
        ans = min(ans, pq.top().X);
    }

    return ans;
}

 

2 - 2. 세그먼트 트리

#include <bits/stdc++.h>

using namespace std;

template<typename T>
class SegmentTree {
    private:
        int n;
        T *tree;
    public:
        SegmentTree(vector<int> &a): n(a.size()) {
            tree = new T[n << 1];
            for(int i = 0; i < n; i++) {
                tree[i + n] = a[i];
            }
            for(int i = n - 1; i > 0; i--) {
                tree[i] = max(tree[i << 1], tree[i << 1 | 1]); 
            }
        }
    
        ~SegmentTree() {
            delete [] tree;
        }
    
        T query(int l, int r) {
            T ret{};
            for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
                if(l & 1) ret = max(ret, tree[l++]);
                if(r & 1) ret = max(ret, tree[--r]);
            }
            return ret;
        }
};

int solution(vector<int> s, int k) {
    SegmentTree<int> segtree(s);
    int st{0}, en{k};
    int ans = segtree.query(st, en);
    while(en < s.size()) {
        ans = min(ans, segtree.query(++st, ++en));
    } 
    return ans;
}