[백준 2170] 선 긋기 (C++)

문제 링크: www.acmicpc.net/problem/2170

2170번: 선 긋기

1. 주의할 점

- 왼쪽에 대한 오름차순으로 정렬 이후, 오른쪽에 대한 오름차순 정렬을 진행한다

- 입력 받을때, 처음 받는 수가 항상 왼쪽에 위치한다고 보장할 수 없다

 

2. 구현

- S(Start)에 대해서 오름차순으로 정렬 -> E(End)에 대해서 오름차순 정렬을 진행하는 우선순위큐를 생성한다

- 각 점에 대해서 입력받을 때, 작은 값을 S, 큰 값을 E에 할당한 이후 우선순위큐에 삽입한다

- 우선순위큐에서 1개의 선분씩 빼면서 시작 선분일 경우 L,R에 시작점과 끝점을 할당한다

- 시작 선분이 아닐 경우, R과 빼낸 선분의 시작점을 비교하여 빼낸 선분의 시작점의 값이 더 크다면 Len에 지금까지의 길이(R-L)만큼 더한 이후, R과 L을 갱신한다

- R과 빼낸 선분의 시작점을 비교하여 빼낸 선분의 시작점의 값이 더 크지 않다면, R과 빼낸 선분의 끝점을 비교하여 큰 값을 R에 할당한다. 빼낸 선분의 끝점을 R에 무조건 할당 할 경우, 틀린다(Ex. 1->4선분, 2->3선분. 답: 3)

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct info {
	int s, e;
};
struct cmp {
	bool operator()(info &a, info &b) {
		if (a.s == b.s)
			return a.e > b.e;
		return a.s > b.s;
	}
};
info tmp;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, a, b;
	cin >> n;
	priority_queue<info, vector<info>, cmp> pq;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		tmp.s = min(a, b);
		tmp.e = max(a, b);
		pq.push(tmp);
	}
	int len = 0;
	int mini = -1000000001;
	int l = mini, r = mini;
	while (!pq.empty()) {
		int cs = pq.top().s;
		int ce = pq.top().e;
		pq.pop();
		if (l == mini) {
			l = cs;
			r = ce;
			continue;
		}
		if (cs > r) {		//안겹칠 때
			len += (r - l);
			r = ce;
			l = cs;
		}
		else
			r = max(r, ce);
	}
	cout << len + (r - l);
	return 0;
}