백준 BOJ 22963 - 3초 정렬

https://www.acmicpc.net/problem/22963

22963번: 3초 정렬

처음 보고 든 생각은 lis였고,

lis에 포함되지 못한 값들을 적당히 변경하면 오름차순으로 만들수 있지 않을까 생각.

https://blog.koderpark.dev/191

백준 BOJ 14003 - 가장 긴 증가하는 부분 수열 5

이 문제에 풀듯이

먼저 lis를 다 구해줬다.

 

여기서 WA를 받았는데,

LIS와 다르게 이 문제는 등호가 포함되어있기 때문에

등호에 맞게 코드를 좀 수정해주었다.

 

그리고 반례를 하나 발견

원래 생각할때 입력받은 값의 오른쪽 끝은 항상 최대값이라 생각했으나,

5

1 2 3 4 1 처럼 입력이 들어올수 있었기에

임의로 입력값에 1e9를 추가해서

N+1사이즈로 만들어 처리해줬다.

이 과정에서 lis안에 포함된 수를 판별하던걸 map으로 짜던것도

중복가능하다는 점 때문에 손을 봤다.

 

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

vector<int> lis;
vector<int> v;
pair<int,int> back[234567];

int ans[234567] = {-1};


int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	
	lis.push_back(-INF);
	
	int N,k;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> k;
		v.push_back(k); 
	}
	
	for(int i=0; i<N; i++){
		if(lis.back() <= v[i]){
			lis.push_back(v[i]);
			back[i] = {v[i], lis.size()-1};
		}else{
			auto it = upper_bound(lis.begin(), lis.end(), v[i]);
			*it = v[i];
			back[i] = {v[i], distance(lis.begin(), it)};
		}
	}
	
	int ptr = lis.size()-1;
	for(int i=N-1; i>=0; i--){
		if(back[i].second == ptr){
			ans[ptr] = back[i].first;
			ptr--;
		}
	}
	
	if(N-lis.size()+1 <= 3) cout << "YES\n";
	else{
		cout << "NO\n";
		return 0;
	}
	v.push_back(1e9);
	cout << N-lis.size()+1 << "\n";
	
	ptr = lis.size()-1;
	for(int i=N-1; i>=0; i--){
		if(v[i] != ans[ptr]){
			cout << i+1 << " " << v[i+1] << "\n";
			v[i] = v[i+1];
		}else{
			ptr--;
		}
	}
	return 0;
}

조금 소스코드가 보기 더럽게 된거같긴한데

일단 이 코드로 AC.