프로그래머스 문제 - 징검다리 건너기

프로그래머스 징검다리 건너기 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

친구들이 징검다리를 건너려고 하며 징검다리의 디딤돌이 stones배열에 나열됩니다.
stones에는 모두 숫자가 적혀 있으며 한 번 밟을 때마다 1씩 줄어들며 0이 되면 밟을 수 없습니다.
디딤돌이 0이 되어 밟을 수 없다면 한번에 k칸을 건너 뛸 수 있습니다. 단 다음으로 밟을 수 있는 디딤돌이 있을 경우 무조건 다음 디딤돌로 건너가야 합니다.
최대 몇 명까지 징검다리를 건널 수 있는지 구해야합니다.

문제 풀이

징검다리를 넘어갈 때 k칸 만큼 0이 되는 순간 중 최솟값을 찾아야 합니다. 그런 부분을 찾기 위해 index가 마지막 디딤돌이라 생각한 후 k만큼 앞에 있는 디딤돌 중 최대값인 값들 중 최솟값을 찾아야 하는 것입니다.

앞과 뒤에서 값을 뺄 수 있어야 하기 때문에 deque컨테이너를 사용하며 최대값이였던 값이 검색하는 k개의 디딤돌에 포함되지 않을 경우 deque에서 제외하기 위하여 index값도 같이 저장해줍니다.

//first : index, second : value
deque<pair<int, int>> dq;

이후 dq.front값보다 현재 보고 있는 값이 더 클 경우 pop_front를 해줍니다. 이는 다음 최대값도 비교해주며 dq.front가 더 클 경우나 컨테이너가 빌 때까지 찾아줍니다.

또한 최대값보다 현재 보고 있는 값이 작더라고 이후 최대값이 빠질 경우를 생각하여 값을 저장해주어야 합니다.
최대값 다음으로 존재할 수 있는 값들을 넣어주어야 하기 때문에 dq.back값과 현재 보고 있는 값을 비교하여 dq.back값이 더 크거나 컨테이너가 빌 때까지 찾아줍니다.

이후 최대값이 k-1의 인덱스를 가지게 된 후부터 최솟값을 찾아주면 되면 O(n)시간복잡도를 가지며 문제를 해결할 수 있습니다.

전체 코드

생각보다 어렵기로 알려진 유명한 문제였으며 이해하고 풀어내기가 쉽지 않았습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 200000001;
    int result = 0;
    //first : index, second : value
    deque<pair<int, int>> dq;
    int cnt = 0;
    
    for(int i = 0; i < stones.size(); i++)
    {
        //만약 디딤돌 중 제일 큰 숫자가 칸 수를 넘어갈 경우 제거
        while(!dq.empty() && dq[0].first < i-k+1)
        {
            dq.pop_front();
        }
        //제일 큰 숫자 다음으로 올 수 있는 최대값을 넣기 위해 작은 수들을 제거
        while(!dq.empty() && dq.back().second < stones[i])
        {
            dq.pop_back();
        }
        dq.push_back(make_pair(i, stones[i]));
        
        //넘어갈 수 없는 칸 수에 도달할 경우부터 최솟값을 찾아줌
        if(i >= k-1 && answer > dq[0].second)
        {
            answer = dq[0].second;
        }
    }
    
    return answer;
}

출저

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