# [Gold V] 데크 소트 2 [문제 링크](https://www.acmicpc.net/problem/10975) ## 문제 설명 <p>데크는 큐와 비슷하지만, 앞과 뒤 양쪽에서 자료를 넣거나 뺄 수 있는 자료구조이다.</p> <p>N개의 수가 주어졌을 때, 첫 번째 수부터 마지막 수까지 순서대로 아래 세 가지 중에 한 방법을 이용해 데크에 넣어야 한다.</p> <ol> <li>수를 존재하는 데크중 하나의 맨 앞에 넣는다.</li> <li>수를 존재하는 데크중 하나의 맨 뒤에 넣는다.</li> <li>새로운 데크를 만들어서 그 곳에 수를 넣는다.</li> </ol> <p>위의 방법을 이용해서 모든 수를 적절히 데크에 넣은 다음, 모든 데크를 적절히 이어 붙여 오름차순으로 만들려고 한다. 이때, 필요한 데크 개수의 최솟값을 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 수의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 한 줄에 하나씩 주어진다. 각 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.</p> ## 출력 <p>첫째 줄에 데크 소트를 할 때, 필요한 데크의 최소 개수를 출력한다.</p> ## 풀이 직접 정렬을 해보고 인덱스가 붙어있는 숫자끼리 한 데크에 존재하도록 구현했습니다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> v(n); for(int i=0;i<n;i++) cin >> v[i]; vector<int> sorted = v; sort(sorted.begin(), sorted.end()); vector<pair<int, int>> range; for(int val : v) { int idx = lower_bound(sorted.begin(), sorted.end(), val) - sorted.begin(); bool chk=false; for(auto &e : range) { if(idx==e.first-1) e.first--, chk=true; else if(idx==e.second+1) e.second++, chk=true; } if(!chk) range.push_back({idx, idx}); } cout << range.size(); } ```