BOJ 10975 - 데크 소트 2

사실 이 문제를 풀때 1624번을 푼다는 전제 하에 풀어보았지만... 1624는 다른 접근 방식으로 풀었다..

 

이 문제는 생각보다 단순한 발상을 가지고 풀 수 있었다.

 

---

 

우선 최소한의 덱을 생성해 수열을 정렬된 상태로 만드는 것이 목표이다.

그렇다면 한가지를 떠올려볼 수 있다.

이미 정렬된 상태의 수열과 비교를 하며 덱에 추가할지 말지를 판별해볼 수 있지 않을까?

 

순서대로 덱에 집어넣어보며 정렬된 수열과 확인하는 방법으로 이 문제를 해결 할 수 있다.

처음에 무조건 덱이 하나 이상 있어야 함으로 덱에는 첫 번째 수가 있고 나머지를 순서대로 넣을지 말지를 정해본다.

 

현재 만들어진 모든 덱을 전부 둘러보며 j번째 덱에서 front와 back의 인덱스값과 i번째 수의 인덱스 값이 1차이가 난다면 인접한 수임을 알 수 있음으로 i번째 수는 j번째 덱에 넣을 수 있다.

만약 정렬된 상태의 현재 값과 비교했는데 덱에 있는 값과 인접하지 않았다면 새 덱을 만든다.

 

모든 수에 대해 확인한 후 덱의 크기가 곧 문제의 정답임을 알 수 있다.

 

#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNING
#define endl "\n"
#define upgrade ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
typedef long long ll;
typedef long double ld;
const int inf = 1e9;
const int mod = 1000000007;
int binsh(vector<pair<int, int>>& arr, int value) {
	int now = 0;
	for (int i = 1; i < arr.size(); i++) {
		if (arr[i].first == value) {
			return arr[i - 1].first;
		}
	}
}
int binsb(vector<pair<int, int>>& arr, int value) {
	for (int i = arr.size() - 1; i >= 1; i--) {
		if (arr[i].first == value) {
			return arr[i + 1].first;
		}
	}
}
int main() {
	upgrade;
	int n;
	cin >> n;
	vector<pair<int,int>>arr(n + 2);//value, index
	arr[0] = { -1001,-1001 };
	arr[n + 1] = { 1010, 1010 };
	for (int i = 1; i <= n; i++) {
		cin >> arr[i].first;
		arr[i].second = i;
	}
	vector<pair<int, int>>temp(arr);
	sort(all(arr));
	vector<deque<pair<int, int>>>dq(1);
	dq[0].push_back(temp[1]);
	for (int i = 2; i <= n; i++) {
		bool check = 0;
		for (int j = 0; j < dq.size(); j++) {
			int now_sorted_value_front = binsh(arr, dq[j].front().first);
			int now_sorted_value_back = binsb(arr, dq[j].back().first);
			if (now_sorted_value_front == temp[i].first) {
				dq[j].push_front(temp[i]);
				check = 1;
				break;
			}
			else if (now_sorted_value_back == temp[i].first) {
				dq[j].push_back(temp[i]);
				check = 1;
				break;
			}
		}
		if (!check) {
			dq.push_back(deque<pair<int, int>>(1, temp[i]));
		}
	}
	cout << dq.size();
	return 0;
}