징검다리 건너기 [Lv. 3]

프로그래머스

징검다리를 이루는 각 디딤돌에는 밟을 수 있는 횟수가 정해져 있습니다. 징검다리를 건널 때에는 밟을 수 있는 디딤돌을 모두 밟고 건너야하며, 한번에 건너뛸 수 있는 디딤돌의 갯수는 k개 입니다. ( 바로 앞에 밟을 수 있는 횟수가 0인 디딤돌이 있을 때 건너 뛸 수 있음 )

 

디딤돌을 밟을 수 있는 횟수들을 배열과 k를 입력받을 때 건널 수 있는 사람의 수를 구하시오.

 

풀이 방법

당연하게도 하나하나 시물레이션을 돌리면 시간 초과가 발생합니다. 그렇기 때문에 어떠한 조건에서 시뮬레이션이 종료되는 지를 생각해보고 그 조건을 이용하여 코드를 작성하면 되겠습니다.

 

시뮬레이션이 종료되는 조건은 연속되는 k개의 디딤돌이 모두 밟을 수 없는 상태가 되는 시점입니다.

즉 k가 3이고 디딤돌이 10개라면 [1, 2, 3], [2, 3, 4], [3, 4, 5], [4, 5, 6] 으로 연속되는 k개의 디딤돌을 정렬 할 수 있겠고

디딤돌 배열에서 가장 작은 [ 모두 밟을 수 없는 상태가 되는 횟수 ]를 찾아야 한다는 것 입니다.

 

시간초과가 뜨는 코드 예시입니다.

#include <string>
#include <iostream>
#include <vector>

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 1000000000;
    
    for (int i = 0; i < stones.size() - k +1; i++)
    {
        int value = 0;
        for (int j = i; j < i + k; j++)
            value = max(value, stones[j]);
        
        answer = min(answer, value);
    }
    return answer;
}

 

 

정답 코드

#include <vector>
#include <deque>
#include <algorithm>
#include <iostream>
using namespace std;

int solution(vector<int> stones, int k) {
    deque<int> dq;
    int answer = 1000000000;

    for (int i = 0; i < stones.size(); i++) {
        
        while(!dq.empty() && stones[dq.back()] <= stones[i])
            dq.pop_back();
        
        dq.push_back(i);
        
        if (dq.front() <= i - k)
            dq.pop_front();
        
        if (i >= k - 1)
            answer = min(answer, stones[dq.front()]);
        
    }

    return answer;
}

시간 초과를 해결하기 위에 deque를 사용했습니다.

가장 큰 수가 항상 front에 올 수 있도록 dq의 뒤에 있는 값이 현재 값보다 작으면 삭제 해줬습니다.

(현재 값보다 작고 왼쪽에 있는 수라면 버려도 되는 수입니다.)

 

만약 front에 있는 수가 범위를 초과했다면 없애주는 코드를 추가해주었고

첫 번째 윈도우가 채워진 이후부터 answer를 업데이트 해주었습니다.