이 튜토리얼에서는 선분의 합집합 길이를 구하는 프로그램을 작성할 것입니다.
선분의 시작점과 끝점이 주어지고 선분의 합집합 길이를 찾아야 합니다.
우리가 사용할 알고리즘을 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
결론
튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.