문제
매우 큰 도화지에 지금부터 선을 그으려고 한다. N번 선을 그을 것이며, 선을 그을 때에는 왼쪽 끝 위치와 오른쪽 끝 위치를 정해서 그 두 점을 잇는 선분을 긋는다. 이때 그어진 선의 전체 길이를 구하는 프로그램을 작성하시오. 즉, 겹쳐서 그린 부분은 한 번만 센다.
입력
첫째 줄에 N이 주어진다. 이후 N개의 줄에 각 선분의 왼쪽 끝과 오른쪽 끝 위치가 주어진다.
- 1 ≤ N ≤ 1,000,000
- -10^9 ≤ 좌표 ≤ 10^9
출력
그어진 선의 전체 길이를 출력한다.
예제
입력:
4
1 3
2 5
3 5
6 7출력:
5풀이
핵심 아이디어: 선분들을 왼쪽 끝 기준으로 정렬한 뒤 스위핑(라인 스위핑)으로 겹치는 구간을 병합한다. 정렬 후 현재 구간의 오른쪽 끝(r)을 유지하면서 다음 선분이 현재 구간과 겹치는지 확인한다.
- 정렬: 모든 선분을 왼쪽 끝 기준 오름차순 정렬한다. 왼쪽 끝이 같으면 오른쪽 끝 기준으로 정렬한다.
- 첫 선분 처리: 첫 선분의 길이를 정답에 더하고, 현재 오른쪽 끝
r을 첫 선분의 오른쪽으로 초기화한다. - 스위핑: 두 번째 선분부터 순서대로 처리한다.
- 현재 선분의 왼쪽 끝이
r이하이면: 겹치는 구간이다. 새로 추가되는 길이max(0, 현재 오른쪽 - r)만큼 정답에 더하고r을 갱신한다. - 현재 선분의 왼쪽 끝이
r보다 크면: 겹치지 않는 새 구간이다. 선분 전체 길이를 더하고r을 갱신한다.
- 현재 선분의 왼쪽 끝이
코드
package day349;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Day329BOJ2170선긋기 {
static class Node {
int l;
int r;
Node(int h, int o) {
l = Integer.min(h, o);
r = h + o - l;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader((new InputStreamReader(System.in)));
int N = Integer.parseInt(br.readLine());
ArrayList<Node> arr = new ArrayList<>();
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
arr.add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
Collections.sort(arr, (A, B) -> A.l == B.l ? A.r - B.r : A.l - B.l);
int ans = arr.get(0).r - arr.get(0).l, r = arr.get(0).r;
for (int i = 1; i < N; i++) {
if (arr.get(i).l <= r) {
ans += Integer.max(0, arr.get(i).r - r);
r = Integer.max(r, arr.get(i).r);
} else {
ans += arr.get(i).r - arr.get(i).l;
r = arr.get(i).r;
}
}
System.out.println(ans);
}
}복잡도
- 시간: O(N log N) — 정렬이 지배적, 스위핑은 O(N)
- 공간: O(N) — 선분 목록 저장