[백준] 2568번: 전깃줄 - 2

📌 문제

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

📌 설명

같은 위치에는 두 개 이상의 전깃줄이 연결되지 않는다. 그렇다면 A 전봇대를 기준으로 정렬 후 B 전봇대에 연결된 위치가 LIS를 이루는 위치들은 서로 교차하지 않는다는 것을 알 수 있다. 즉, 풀이 순서는 다음과 같다.

1. A 전봇대 위치를 기준으로 정렬한다.

2. B 전봇대 위치에 대하여 LIS를 구한다.

3. LIS에 해당하지 않는 전깃줄의 개수 및 위치를 구한다. 이는 우리가 출력해야 하는 답이다.

출력 시 B 전봇대의 위치를 출력하지 않도록 주의한다. A 전봇대의 위치를 출력해야 한다.

📌 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int lis_idx[500001];
int conn[500001]; // conn[i] = j: B전봇대의 i번과 A전봇대의 j번이 연결됨

int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ a,b });
		conn[b] = a;
	}

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

	vector<int> end, lis;
	for (int i = 0; i < n; i++) {
		end.push_back(v[i].second);
	}

	for (int i = 0; i < n; i++) {
		int idx = lower_bound(lis.begin(), lis.end(), end[i]) - lis.begin();

		if (idx == lis.size())
			lis.push_back(end[i]);
		else
			lis[idx] = end[i];

		lis_idx[i] = idx;
	}

	int cur = lis.size() - 1;
	vector<int> not_lis;
	for (int i = n - 1; i >= 0; i--) {
		if (cur != lis_idx[i]) {
			not_lis.push_back(conn[end[i]]);
		}
		else
			cur--;
	}

	cout << not_lis.size() << "\n";
	sort(not_lis.begin(), not_lis.end());
	for (int i = 0; i < not_lis.size(); i++) {
		cout << not_lis[i] << "\n";
	}
}