📖 문제 읽기

정수로 이루어진 쿼리가 주어졌을 때, 이 정수들로 beautiful array를 구성하는 것이 목표이다. 이때 beautiful array란 다음과 같다.

• 배열의 시작부터 연속된 특정 개수(0개일 수 있다)의 원소를 떼어서 그 배열의 뒤에 그대로 붙였을 때 배열의 원소들이 단조증가(a1 ≤ a2)하면 그 배열은 beautiful array이다.

• 원소가 0개 이거나 1개인 배열은 beautiful array이다.

초기에 비어있는 배열을 쿼리로 들어온 정수로 채워나가야 하는데, 매 쿼리의 결과를 1또는 0로 나타내야 한다. 이때 1은 쿼리로 들어온 정수를 배열의 뒤에 붙이는 경우이고 0은 붙이지 않고 넘어가는 경우이다.

📊 문제 분석

위에서 언급한 beautiful array의 조건들을 보면 beautiful array의 종류는 다음과 같다.

• 원소가 0개인 배열

• 원소가 1개인 배열

• 원소가 n개이며 배열의 원소들이 처음부터 끝까지 단조증가하는 배열

• 원소가 n개이며 배열의 원소들이 단조증가하는 부분이 두 부분으로 나뉘며 나뉘는 부분에서 앞의 원소가 바로 뒤의 원소보다 큰 배열

💡 아이디어 도출

문제를 분석한 바와 같이 배열을 구성하기 위해서는 총 다섯 가지 경우에 따라 쿼리를 수행하면 된다.

1. 원소 간 감소가 발생하지 않았을 때

   1. 쿼리로 들어온 정수가 마지막으로 배열에 들어간 정수보다 크거나 같다 : 1

   2. 쿼리로 들어온 정수가 마지막으로 배열에 들어간 정수보다 작고 배열의 첫 번째 원소보다 작거나 같다 : 1

   3. 쿼리로 들어온 정수가 마지막으로 배열에 들어간 정수보다 작고 배열의 첫 번째 원소보다 크다 : 0

2. 원소 간 감소가 1회 발생했을 때

   1. 쿼리로 들어온 정수가 마지막으로 배열에 들어간 정수보다 크거나 같고 배열의 첫 번째 원소보다 작거나 같다 : 1

   2. 그 외의 경우 : 0

⌨️ 코드

#include <bits/stdc++.h>
 
using namespace std;
 
string solve(){
    int q, a1, a2, start;
    bool desc = false;
    string ans="";
 
    cin>>q;
    for(int i=0;i<q;i++){
        scanf("%d", &a2);
        if(i==0){
            start = a2;
            a1 = a2;
        }
 
        if(!desc){
            if(a1 <= a2) ans += "1";
            else if(start >= a2){
                desc = true;
                ans += "1";
            }
            else{
                ans += "0";
                continue;
            }
        }
        else{
            if(a1 <= a2 && start >= a2) ans += "1";
            else{
                ans += "0";
                continue;
            }
        }
 
        a1 = a2;
    }
 
    ans+="\n";
    return ans;
}
 
int main()
{
    int t;
 
    cin>>t;
    while(t--){
        cout<<solve();
    }
}