프로그래머스 - 징검다리 건너기(2019 카카오 개발자 겨울 인턴십)

우선 stones의 배열의 크기가 20만까지 이므로 O(N^2)으로는 효율성 검사를 통과할 수 없다.

그래서 set을 이용하여 풀어보았다. 

 

코드

#include <string>
#include <vector>
#include <iostream>
#include <set>
using namespace std;
multiset<int, greater<int> > s;
int solution(vector<int> stones, int k) {
    int answer = 0;
    int start = 0;
    for(int i=0; i<k; i++)
        s.insert(stones[i]);
    set<int>::iterator it;
    it = s.begin();
    int final_max = *it;
    for(int i=0; i< stones.size() - k; i++)
    {
        it = s.find(stones[i]);
        s.erase(it);
        s.insert(stones[i + k]);
        it = s.begin();
        if (final_max > *it)
            final_max = *it;
    }
    return final_max;
}

stones 배열에서 앞에서부터 k개 씩 뽑아 연속되는 k개에서 발판의 최댓값을 구하고 n - k + 1개 구간의 최댓값들의 최솟값을 구하면 몇 명이 건너갈 수 있는지 구할 수 있다. 

 

k개 씩 뽑는 이유는 k개의 최댓값을 넘어가는 경우 한 번에 k칸을 뛰어넘을 수 없기 때문에 이러한 방식으로 set에 추가하고 삭제하는 과정을 통해 최댓값의 최솟값을 찾아주면 된다.