[백준] 2568 전깃줄 - 2

백준 2568 전깃줄 - 2

• https://www.acmicpc.net/problem/2568
• 없애야 하는 전깃줄의 최소 개수 = 전체 전깃줄의 개수 - LIS의 길이
• 없애야 하는 전깃줄의 배열을 구해야하므로 LIS를 구할 때와 반대로
  -> record 배열의 제일 뒤부터 탐색하여
  -> record[i]에 저장된 인덱스가 순차적인 내림차순이 되지 않는 경우
  -> ret 벡터에 push_back(line[i].first) 연산을 한다.

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

bool cmp(const pair<int, int> &a, const pair<int, int> &b){
	return a.first < b.first;
}

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

	vector <pair<int, int>> line;

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int left, right;
		cin >> left >> right;
		line.push_back(make_pair(left, right));
	}
	sort(line.begin(), line.end(), cmp);

	vector <int> vt;
	vector <int> record;
	vector <int> ret;

	// record 벡터에 line[i].second가 vt벡터에 저장되는 위치 저장 
	int idx = 0;
	vt.push_back(line[0].second);
	record.push_back(0);

	for (int i = 1; i < n; i++) {
		if (vt.back() < line[i].second) {
			vt.push_back(line[i].second);
			record.push_back(++idx);
		}
		else {
			auto it = lower_bound(vt.begin(), vt.end(), line[i].second);
			*it = line[i].second;
			record.push_back(it-vt.begin());
		}
	}

	// lis가 아닌 값 추적
	int flag = idx;
	for (int i = n-1 ; i >= 0; i--) {
		if (record[i] == flag) 
			flag--;
		else 
			ret.push_back(line[i].first);
	}
	reverse(ret.begin(), ret.end());

	//결과
	cout << n - idx - 1<<"\n";
	for (auto it = ret.begin(); it != ret.end(); it++)
		cout << *it << "\n";

	return 0;
}