codeforces #591 D - Sequence Sorting (LIS유사, 투포인터, dp)

https://codeforces.com/contest/1241/problem/D

 

최대 300000의 쿼리에 대해서 최대 300000길이의 배열을 입력받고 문제에 나온 연산을 최소한으로 수행해서 배열을 정렬한다면, 그 연산의 횟수를 출력하는 문제다.

 

초기의 배열을 A(앞으로 미는 연산 수행한 그룹) + B(연산수행하지않은 그룹) + C(뒤로 미는 연산을 수행한 그룹)으로 나눈다면, A의 크기와 C의 크기의 합이 정답이 된다. (여기서 크기는 그룹에 속한 숫자의 종류개수)

 

A크기+C크기 = 초기배열의 크기 - B그룹의 크기    이므로, B그룹의 크기만 계산해주면 된다.

 

B그룹은 초기 배열에서 이미 정렬된 최대의 길이이므로, LIS와 유사하다고 볼 수 있다.

 

(초기배열이 1 3 1 4라면 LIS=3, 정렬된 최대길이=2 이다. LIS와 유사하지만 더 빠른 방법으로 구할 수 있다.)

 

먼저 배열의 각 숫자마다 제일 먼저 등장한 index를 저장할 l배열과, 제일 마지막으로 등장한 index를 저장하는 r배열을 만들어 두면 시간복잡도를 줄일 수 있다.

 

https://codeforces.com/blog/entry/70358

더 자세한 설명은 댓글의 dantrag님의 설명을 읽어보자

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 300001;
const int INF = 1e9;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int q; cin >> q;
	while (q--) {
		int n; cin >> n;
		int arr[MAX], l[MAX],r[MAX];
		fill(l, l + MAX, INF);
		fill(r, r + MAX,-INF);
		vector<int> v;
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
			v.push_back(arr[i]);
			l[arr[i]] = min(l[arr[i]], i);
			r[arr[i]] = max(r[arr[i]], i);
		}

		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());

		int res = n;
		int dp[MAX] = { 0 };
		dp[0] = 1;
		for(int i=0; i<v.size()-1; i++){
			if (r[v[i]] > l[v[i + 1]])
				dp[i+1] = 1;
			else 
				dp[i+1] = dp[i] + 1;
			res = min(res, (int)v.size() - dp[i+1]);
		}
		cout << res << '\n';

	}
}

 

사실 이 코드를 제출하면 time limit이 뜬다. editorial의 공식 solution 코드와 무슨 차이인지 모르겠다

 

 

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 99;
const int INF = int(1e9) + 99;

int t, n;
int a[N];
int l[N], r[N];
int dp[N];

int main() {
	scanf("%d", &t);
	for(int tc = 0; tc < t; ++tc){
		scanf("%d", &n);
		for(int i = 0; i < n; ++i){
			l[i] = INF;
			r[i] = -INF;
			dp[i] = 0;
		}

		vector <int> v;	
		for(int i = 0; i < n; ++i){
			scanf("%d", a + i);
			--a[i];
			v.push_back(a[i]);
			l[a[i]] = min(l[a[i]], i);
			r[a[i]] = max(r[a[i]], i);
		}

		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
	
		int res = n;
		for(int i = v.size() - 1; i >= 0; --i){
			if(i + 1 == v.size() || r[v[i]] >= l[v[i + 1]]) dp[i] = 1;
			else dp[i] = 1 + dp[i + 1];
			res = min(res, int(v.size())- dp[i]);
		}

		printf("%d\n", res);
	}	

	return 0;
} 

공식 코드