[BOJ] 세워라 반석 위에 21967번 C++

 

문제

드높은 남산 위에 우뚝 선

(중략)

세워라 반석 위에

선린의 터를

반석: 넓고 펀펀한 큰 돌, 너럭바위

어떤 수열이 반석이라는 것은, 수열의 최댓값과 최솟값의 차이가 2 이하임을 의미한다.

예를 들어 1 2 3 3 1 2는 최댓값(3)과 최솟값(1)의 차이가 2이므로 반석이고, 2 6 5 4는 최댓값(6)과 최솟값(2)의 차이가 4이므로 반석이 아니다.

수열이 주어지면 수열의 연속한 부분 수열(부분 문자열, substring) 중, 가장 긴 반석의 길이를 구하는 프로그램을 작성하자.

입력

첫 번째 줄에 수열의 길이 N$N$이 주어진다.

두 번째 줄에는 수열 A의 원소 A1,A2,⋯,AN이 공백으로 구분되어 주어진다.

출력

수열 A의 연속한 부분 수열 중 가장 긴 반석의 길이를 출력한다.

 

접근 방식

 

투 포인터를 사용하면 될 것 같다고 생각했는데 생각보다 어려웠다

최대, 최소값을 계속 갱신하면서 포인터를 이동해야 하기 때문에 이를 위해 찾아보다가 

deque 자료구조를 사용하여 내림차순 덱과 오름차순 덱을 각각 최댓값, 최소값을 관리할 수 있도록 코드를 작성하였다

 

단, 덱에는 배열의 값이 아닌 배열의 인덱스를 저장해놓아야 왼쪽 포인터를 이동할 때 최대-최소 = 2를 만족시킬 수 있다!

 

코드

#include<bits/stdc++.h>
using namespace std;

int main() {
    int N; cin>>N;
    vector<int> v(N);
    for(int i=0; i<N; i++) cin>>v[i];

    deque<int> mnDq, mxDq;
    int s=0, ans = 0;


    for(int e=0; e<N; e++) {

        while(!mxDq.empty() && v[mxDq.back()] <= v[e]) mxDq.pop_back(); // 내림차순
        mxDq.push_back(e);

        while(!mnDq.empty() && v[mnDq.back()] >= v[e]) mnDq.pop_back(); // 오름차순
        mnDq.push_back(e);

        while(!mxDq.empty() && !mnDq.empty() && v[mxDq.front()] - v[mnDq.front()] > 2) {
            s++;
            if(mxDq.front() < s) mxDq.pop_front();
            if(mnDq.front() < s) mnDq.pop_front();
        }

        ans = max(ans, e-s+1);
        
    }

    cout<<ans;

}