스위핑. [2170]

[1. 문제 설명]
선을 여러번 그었을 때, 그어진 선의 총길이를 구한다.

중복되어 그어진 구간은 한번만 계산해야 한다.

---

[2. 풀이 접근]

단순한 풀이로는 절대 시간내 해결 할 수 없다.

겹치는 구간등을 확인해야 할 때, 그 범위가 너무 넓기 때문이다.

(문제 입력 상 구간의 최대 길이는 20억)

 

그림을 좀 그리다보면 풀이에 대한 실마리가 조금 잡힌다.

 

// 여기에 그림이 필요..

 

즉, 모든 구간을 X 를 기준으로 정렬 하면,

순차적으로 탐색하다보면

X 를 시작으로 하여 선을 그었을 때 겹쳐지는 최대 구간을 알 수 있다.

=> 자신보다 뒤에오는 구간의 시작 점은 자신보다 앞에 위치 할 수 없다.

=> 지금까지 업데이트 한 구간 내에 있거나, 그 구간을 좀 더 확장시키거나, ...

 

여기서 중요한 점은

새로운 구간이 지금까지 업데이트 한 구간과 겹치는 구간이 존재하지 않을 때 이다.

=> 구간의 시작 점이 현재 까지의 최대 구간보다 뒤에 오는 경우이다.

 

이때는, 기존의 최대 구간의 길이를 더하고,

업데이트 할 구간을 현재 구간으로 갱신해야 한다.

 

전체 시간복잡도는 정렬에 의해 지배 되므로

O(NlogN) 이다.

---

[3. 코드]