[C++] 백준 2568 전깃줄 2

#include <iostream>
#include <algorithm>
#include <vector>
 
int n = 0;
std::vector<std::pair<int, int>> pair = {};
std::vector<int> vec = {};
int ansreverse[100001] = {};
 
int main() 
{	
	std::cin >> n;
	for (int i = 0; i < n; ++i) 
	{
		int A = 0;
		int B = 0;
		std::cin >> A >> B;
		pair.push_back({ A,B });
	}
 
	std::sort(pair.begin(), pair.end());
 
	int temp = 0;
 
	for (int i = 0; i < pair.size(); ++i)
	{
		if (vec.empty())
		{
			vec.push_back(pair[i].second);
			ansreverse[i] = 1;
		}
 
		else
		{
			if (vec[vec.size() - 1] < pair[i].second)
			{
				vec.push_back(pair[i].second);
				ansreverse[i] = vec.size();
			}
 
			else
			{
				auto iter = std::lower_bound(vec.begin(), vec.end(), pair[i].second);
				*iter = pair[i].second;
				ansreverse[i] = iter - vec.begin() + 1;
			}
		}
 
		if (ansreverse[i] > temp)
		{
			temp = ansreverse[i];
		}
	}
 
	std::cout << pair.size() - vec.size() << "\n";
 
	int index = vec.size();
	std::vector<int> ans = {};
	for (int i = n - 1; i >= 0; --i)
	{
		if (ansreverse[i] != index)
		{
			ans.push_back(pair[i].first);
		}
 
		else
			--index;
	}
 
	for (int i = ans.size() - 1; i >= 0; --i)
	{
		std::cout << ans[i] << "\n";
	}
 
	return 0;
}
 

이전에 풀어본 가장 긴 증가하는 부분 수열과 비슷합니다.

증가하는 수열과 비슷하기에 lower_bound를 사용해서 본인보다 초과한 자리 앞을 구해서 바꿔치는데,

그 때 본인의 순서를 기억합니다. 가장 앞쪽이라면 1, 맨 뒤라면 n입니다.

그렇게 되면 순서를 알 수 있기 때문에 순서에 맞지 않는 것들만 ans로 넣어주고 뒤로부터 출력합니다.