이번에는 백준 2170번 선 긋기 문제를 풀어보았습니다.
여러 개의 선분이 주어졌을 때, 서로 겹치는 부분은 한 번만 계산하여 전체 길이를 구해야 합니다.
선분들을 시작점 기준으로 정렬한 뒤, 현재까지 이어지고 있는 구간을 하나로 합쳐가며 길이를 계산하는 방식으로 해결하였습니다.
문제 설명
수직선 위에 N개의 선분이 주어집니다.
각 선분은 시작점과 끝점으로 주어지며, 여러 선분이 서로 겹칠 수 있습니다.
겹쳐서 여러 번 그어진 부분은 한 번만 계산해야 하므로, 모든 선분의 합집합 길이를 구하는 문제입니다.
풀이 아이디어
먼저 모든 선분을 시작점 기준으로 오름차순 정렬합니다.
이후 현재까지 이어지고 있는 하나의 구간을
[st, ed]형태로 관리합니다.
다음 선분을 확인하면서
- 다음 선분의 시작점이
ed보다 크다면 현재 구간과 이어지지 않는 새로운 구간입니다. - 그렇지 않다면 현재 구간과 겹치거나 이어지는 선분이므로
ed만 필요에 따라 늘려줍니다.
새로운 구간이 시작될 때마다 이전 구간의 길이인 ed - st를 정답에 더합니다.
마지막 구간은 반복문이 끝난 뒤 한 번 더 더해줍니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N;
vector<pair<int, int>> inp;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
for (int i=0; i<N; i++) {
int st,ed;
cin >> st >> ed;
inp.push_back({st,ed});
}
sort(inp.begin(), inp.end());
int ret=0;
int st=inp[0].first,ed=inp[0].second;
for (int i=1; i<N; i++) {
if (inp[i].first > ed) {
ret += (ed-st);
st = inp[i].first;
ed = inp[i].second;
} else {
if (ed < inp[i].second) ed = inp[i].second;
}
}
ret += (ed-st);
cout << ret << '\n';
return 0;
}풀이 흐름
-
N개의 선분을 입력받습니다. -
선분을 시작점 기준으로 오름차순 정렬합니다.
-
첫 번째 선분의 시작점과 끝점을
st,ed로 설정합니다. -
두 번째 선분부터 차례대로 확인합니다.
-
다음 선분의 시작점이 현재
ed보다 크다면 현재 구간과 떨어져 있는 새로운 구간입니다. -
기존 구간의 길이
ed - st를 정답에 더합니다. -
새로운 선분을 기준으로
st,ed를 다시 설정합니다. -
다음 선분이 현재 구간과 겹친다면 끝점이 더 큰 경우에만
ed를 갱신합니다. -
모든 선분을 확인한 뒤 마지막으로 남아 있는 구간의 길이를 정답에 더합니다.
-
전체 길이를 출력합니다.
구현 포인트
1. 선분 정렬
sort(inp.begin(), inp.end());pair<int, int>는 기본적으로 첫 번째 값인 시작점을 기준으로 오름차순 정렬됩니다.
시작점이 같다면 끝점을 기준으로 정렬됩니다.
이렇게 정렬하면 왼쪽에 있는 선분부터 차례대로 확인할 수 있기 때문에 현재 구간과 다음 선분이 겹치는지만 확인하면 됩니다.
2. 현재 이어지고 있는 구간 저장
int st=inp[0].first,ed=inp[0].second;st와 ed는 현재까지 겹치거나 이어지는 선분들을 하나로 합친 구간을 의미합니다.
즉,
st : 현재 이어지는 구간의 시작점
ed : 현재 이어지는 구간의 끝점입니다.
3. 새로운 구간이 시작되는 경우
if (inp[i].first > ed) {다음 선분의 시작점이 현재 구간의 끝점 ed보다 크다면 두 선분 사이에는 빈 공간이 존재합니다.
예를 들어 현재 구간이
[1, 5]이고 다음 선분이
[8, 10]이라면 서로 겹치지 않습니다.
따라서 현재까지 만들어진 구간의 길이를 정답에 더합니다.
ret += (ed-st);이후 새로운 선분을 기준으로 다시 구간을 시작합니다.
st = inp[i].first;
ed = inp[i].second;4. 선분이 겹치는 경우
else {
if (ed < inp[i].second)
ed = inp[i].second;
}다음 선분의 시작점이 현재 ed 이하라면 현재 구간과 겹치거나 연결되어 있습니다.
이때는 새로운 길이를 바로 더하지 않고 하나의 구간으로 계속 합칩니다.
예를 들어
현재 구간 : [1, 5]
다음 선분 : [3, 8]이라면 합쳐진 구간은
[1, 8]이 됩니다.
따라서 끝점만 8로 갱신합니다.
5. 현재 선분이 기존 구간 안에 완전히 포함되는 경우
예를 들어 현재 구간이
[1, 10]이고 다음 선분이
[3, 7]이라면 다음 선분 전체가 이미 현재 구간에 포함되어 있습니다.
이 경우
if (ed < inp[i].second)조건이 거짓이므로 아무것도 변경하지 않습니다.
현재 st, ed를 그대로 유지하면 됩니다.
6. 끝점이 같은 경우
다음 선분의 시작점이 현재 끝점과 정확히 같은 경우도 하나의 이어진 선으로 볼 수 있습니다.
예를 들어
[1, 5]
[5, 10]은 전체 길이가
10 - 1 = 9가 됩니다.
코드에서는 새로운 구간을 만드는 조건을
inp[i].first > ed로 두었기 때문에 시작점과 ed가 같은 경우에는 else로 들어가 하나의 구간으로 합쳐집니다.
7. 반복문 안에서 바로 길이를 더하지 않는 이유
겹치는 선분이 계속 등장할 수 있기 때문에 하나의 선분을 확인할 때마다 길이를 더하면 중복 계산이 발생할 수 있습니다.
예를 들어
[1, 5]
[3, 8]
[6, 10]이라면 세 선분은 결국
[1, 10]이라는 하나의 구간입니다.
따라서 현재 구간이 끝났다고 확정되는 순간에만
ret += (ed-st);를 수행합니다.
8. 마지막 구간 처리
ret += (ed-st);반복문에서는 새로운 구간이 시작될 때 이전 구간의 길이를 더합니다.
따라서 가장 마지막 구간은 뒤에 새로운 구간이 없기 때문에 반복문 내부에서 정답에 추가되지 않습니다.
이를 위해 반복문이 끝난 뒤 마지막 구간의 길이를 한 번 더 더해줍니다.
9. 구간 병합
이 문제의 핵심은 정렬된 선분들을 하나씩 확인하면서 겹치는 구간을 계속 합치는 것입니다.
전체 흐름은 다음과 같습니다.
선분 정렬
→ 첫 번째 선분을 현재 구간으로 설정
→ 다음 선분 확인
→ 겹침 : 끝점 확장
→ 안 겹침 : 현재 길이 추가 후 새로운 구간 시작
→ 마지막 구간 길이 추가즉, 대표적인 구간 병합(Interval Merge) 방식으로 해결할 수 있습니다.
시간복잡도
N개의 선분을 정렬하는 데
O(N log N)의 시간이 필요합니다.
정렬 이후에는 모든 선분을 한 번씩 확인하므로
O(N)이 추가됩니다.
따라서 전체 시간복잡도는
O(N log N)입니다.
N이 최대 1,000,000이므로 정렬 이후 한 번의 순회만으로 처리하는 방식이 적절합니다.
