니니즈 친구들이 징검다리를 건너려고 하는데, 한 친구가 징검다리를 건너면 디딤돌의 숫자가 하나씩 줄어들고, 디딤돌의 숫자가 0이 되면 해당 디딤돌은 건너뛰어야 한다. 한 번에 건너뛸 수 있는 디딤돌의 최대 칸 수가 k로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는 지를 구하는 문제이다.
처음에는 for문을 돌면서 각 k크기의 구간마다 최댓값을 구하고, 그 최댓값 중의 최솟값을 구하는 방법으로 문제를 풀었다. 이렇게 제출했을 때, 정확성 테스트는 통과했지만, 효율성 테스트는 통과하지 못했다.
방법을 찾던 중, deque를 이용해서 풀어야 한다는 자료를 보고 deque를 이용해서 풀어보았다. 이 풀이의 핵심은 deque의 front를 항상 최댓값으로 유지해야 한다는 점이다.
위와 같이 징검다리가 주어지고, K가 3일 때, 먼저 deque에 맨 앞 칸을 넣어준다.
그 다음 칸인 4가 2보다 크기 때문에 2를 pop하고 4를 넣어준다. 그 다음 칸인 5에 대해서도 똑같이 반복한다.
5는 3번째 index이고, K는 3이기에 현재 최댓값은 5이다.
다음 칸인 3, 2를 차례로 deque에 넣어주고, 현재 5가 K배열의 맨 앞이기 때문에 pop을 해준다.
1을 넣고, 현재 최댓값이 3이면서 기존의 최댓값이던 5보다 작기 때문에 현재 최댓값을 3으로 바꿔준다.
4는 기존 deque의 back 값보다 크기 때문에 모두 pop하고 4를 넣고, 현재 최댓값인 4가 3보다 크기에 패스한다. 이와 같은 과정으로 반복하면 정답은 3이 나오게 된다.
이를 코드로 작성하면 아래와 같다.
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
int solution(vector<int> stones, int k) {
int answer = 200000000;
deque<int> dq;
for(int i=0;i<stones.size();i++)
{
while(dq.size()>0 && dq.back()<stones[i])
{
dq.pop_back();
}
dq.push_back(stones[i]);
if(i>=k-1)
{
if(answer>dq.front()) answer = dq.front();
if(dq.front()==stones[i-k+1]) dq.pop_front();
}
}
return answer;
}