C++ / 프로그래머스 / 징검다리 건너기

문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/64062

프로그래머스

문제풀이

 

돌이 연속으로 k개가 무너지는 때를 구하는 문제이다.

다른 곳에서 돌이 몇 개가 무너지든 상관이 없다, 오직 k개가 연속으로 무너지는 돌을 구하면 된다.

따라서 구간을 구해서 탐색을 하면 된다.

 

k개가 무너져야 하므로 시작과 끝 안에 있는 돌들은 k개가 된다.

원하는 돌을 없앨 수 있고, 순서대로 정렬을 할 수 있는 multiset을 이용한다.

multiset에 k개의 돌을 집어넣고, 그중 가장 큰 돌을 answer에 저장한다. (multiset은 greater를 통해 내림차순으로 정렬함)

 

그다음 right부분이 돌 끝까지 가도록 하고, 한 번 반복을 하면 시작 지점, 끝 지점을 오른쪽으로 한 칸씩 옮긴다.

left부분을 multiset에서 지울 건데 중복된 값이 있으면 다 지워지므로 find를 통해 하나만 찾고 지운다.

그다음 right부분을 multiset에 입력한다.

multiset의 처음을 가리키는 iter을 선언하고 iter의 값과 answer 중 작은 값을 answer에 저장한다.

코드

#include <string>
#include <vector>
#include <set>
using namespace std;

int solution(vector<int> stones, int k) {
    int answer(0), idx(0), left(0), right(0);
    multiset<int, greater<int>>ms;
    for (right = 0; right < k; ++right) {
        ms.insert(stones[right]);
    }

    auto iter = ms.begin();
    answer = *iter;

    for (right; right < stones.size(); ++right, ++left) {
        ms.erase(ms.find(stones[left]));
        ms.insert(stones[right]);
        iter = ms.begin();
        answer = min(answer, *iter);
    }

    return answer;
}