<Baekjoon> #2170 선 긋기 (Making an Line) c++

가장 유명한 계산 기하 알고리즘 디자인 패턴으로 흔히 sweeping algorithm은 line sweeping 이라고도 불리고, 평면 스위핑을 이용하는 알고리즘들은 수평서 혹은 수직선으로 주어진 평면을 '쓸고 지나가면서' 문제를 해결한다.

문제에 있는 예시를 보면 길이 (1,3), (2,5), (3,5), (6,7)인 선분이 4개 있다. 이를 그림으로 그려보면 아래와 같다.

여기서 선이 여러 번 그려진 곳은 한 번씩만 계산한 그려진 선의 총 길이는 (1,5), (6,7) 길이 합인 5이다.

신경써야 할 부분은 선을 그을 때 선택할 두 점의 위치 (x,y)를 받고 x의 값을 기준으로 오름차순으로 정렬한 뒤 문제를 해결해야 한다.

struct Line {
	int start;
	int end;
};

Line line[MAX];

먼저 한 선분당 점 2개를 입력받아야 하므로 선분의 시작 지점 (start), 끝 지점 (end)를 받는 Line 구조체를 만든다.

bool compare(Line A, Line B){
	if (A.start < B.start) return true;
	return false;
}

void solution() {
	sort(line + 1, line + N + 1, compare);
	int answer = 0;
	int left = -INF;
	int right = -INF;

	for (int i = 1; i <= N; i++) {
		if (line[i].start <= right)
			right = max(right, line[i].end);
		else {
			answer += right - left;
			left = line[i].start;
			right = line[i].end;
		}
	}
    answer += right - left;
}

line에 값을 입력 받은 뒤 line[i].start 을 기준으로 오름차순으로 정렬한다.

현재 line[i].start 지점이 right보다 작거나 같다는 말은 지금의 left, right로 지정된 부분과 겹친다는 의미이다.

즉 그림에서 빨간 선까지 그었을 때 left=1, right=3이다.
새롭게 주황선이 들어왔을 때 주황선.start=2, 주황선.end=5이다.
여기서 주황선의 start는 right보다 작지만 주황선의 end인 5는 right인 3보다 크다. 따라서 right를 5로 갱신해준다.

만약 범위 밖 새로운 선분이 들어왔다면 이전의 left, right를 기준으로 선분의 길이를 answer에 저장하고 새롭게 left, right를 갱신해준다.

여기서 sort와 compare함수에 대해 보자.

1. sort(start, end) : [start, end) 범위의 인자를 오름차순 (기본값, default)으로 정렬해준다.
2. sort(start, end, compare)를 이용하면 사용자가 정한 함수 (compare)를 기준으로 정렬하게 된다.
3. sort(start end, greater<자료형>())를 이용하면 [start, end)범위의 인자를 내림차순으로 정렬해준다.

우리는 line[i].start 를 기준으로 정렬해야 하기 때문에 2번 경우를 사용하면 아주 편리하게 정렬이 가능하다.

근데 자꾸 시간 초과가 떠서 다른 사람들이 한 코드를 봤더니 struct로 선언하지 않고 vector<pair<int, int>> 형식을 사용해서 혹시 이게 문제인가 해서 나도 따라해봤다.

pair<[Type],[Type]>은 2개의 각각 지정한 타입의 값을 저장하고,
저장한 값은 .first .second로 각각 접근할 수 있다.
2개의 연관된 값을 같이 저장할 수 있어서 관리를 용이하게 할 수 있다.
특히 연관된 2개의 값에서 각각의 조건에 따라 정렬한 결과를 얻고자 할 때 사용하면 좋다고 한다. 이 경우에 딱 알맞은 타입이라서 많은 사람들이 사용했나보다.

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

using namespace std;

int N;
vector<pair<int, int>> v;

void input() {
	cin >> N;
	int s, e;
	for (int i = 0; i < N; i++) {
		cin >> s >> e;
		v.push_back({ s,e });
	}
}

void solution() {
	sort(v.begin(), v.end());

	int left = v[0].first;
	int right = v[0].second;
	long long answer = 0;

	for (int i = 1; i < N; i++) {
		if (v[i].first <= right) {
			right = max(right, v[i].second);
		}
		else {
			answer += right - left;
			left = v[i].first;
			right = v[i].second;
		}
	}
	answer += right - left;
	cout << answer << endl;
}
int main() { 
	input();
	solution();

	return 0;
}

전체 코드는 앞에서 struct로 선언한 것과 별반 다르지 않고 시간초과는 계속 뜬다.. 도대체 왜일까 아직도 못찾았다.