이 튜토리얼에서는 선분의 합집합 길이를 구하는 프로그램을 작성할 것입니다.
선분의 시작점과 끝점이 주어지고 선분의 합집합 길이를 찾아야 합니다.
우리가 사용할 알고리즘을 klee 알고리즘이라고 합니다.
문제를 해결하는 단계를 살펴보겠습니다.
- 모든 세그먼트의 좌표로 배열을 초기화합니다.
- 세그먼트 배열의 두 배 크기로 포인트라는 벡터를 초기화합니다.
- 세그먼트 배열을 반복합니다.
- 인덱스 i * 2에 있는 포인트 배열의 값을 현재 세그먼트의 첫 번째 포인트로 채우고 false로 채웁니다.
- 인덱스 i * 2 + 1에 있는 점 배열의 값을 현재 세그먼트의 두 번째 점으로 채우고 거짓입니다.
- 포인트 배열을 정렬합니다.
- 카운터 변수로 포인트 배열을 반복합니다.
- 카운터가 0보다 크면 결과에 i의 첫 번째 점과 i - 1을 추가합니다.
- 두 번째 포인트가 있으면 카운터를 감소시키고 그렇지 않으면 증가시킵니다.
- 결과를 반환합니다.
예시
코드를 봅시다.
#include<bits/stdc++.h>
using namespace std;
int segmentUnionLength(const vector<pair <int,int>> &segments) {
int n = segments.size();
vector<pair<int, bool>> points(n * 2);
for (int i = 0; i < n; i++) {
points[i*2] = make_pair(segments[i].first, false);
points[i*2 + 1] = make_pair(segments[i].second, true);
}
sort(points.begin(), points.end());
int result = 0, count = 0;
for (int i = 0; i < n * 2; i++){
if (count) {
result += points[i].first - points[i-1].first;
}
points[i].second ? count-- : count++;
}
return result;
}
int main() {
vector<pair<int,int>> segments;
segments.push_back(make_pair(1, 3));
segments.push_back(make_pair(2, 7));
segments.push_back(make_pair(6, 12));
segments.push_back(make_pair(13, 5));
cout << segmentUnionLength(segments) << endl;
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
6
결론
튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.