스위핑 알고리즘

스위핑 알고리즘이란?

스위핑(sweeping) : 청소하다, 휩쓸다

스위핑 알고리즘이란 단어의 뜻 그대로 휩쓸고 지나가며 문제를 해결하는 방식으로, 특정 기준에 따라 정렬한 후 순서대로 처리하는 알고리즘이다.

여러 문제를 풀어보았는데 보통 N = 100000 정도가 주어지고, 선분의 겹침 처리 문제가 많이 나오는 것 같고 시간 복잡도는 정렬의 시간복잡도인 NlogN이 대부분이다.(백준 골드 기준)

간단한 날짜 전처리 + 그리디(정렬 기준 중요) + 스위핑 문제이다.

먼저, 월과 일로 주어지는 시작, 끝 점을 1 ~ 365 사이의 수로 전처리하는 과정이 필요하다.

각 점들을 직선 상의 선분들로 나타낸 뒤 시작점의 오름차순, 끝점의 내림차순으로 정렬해 스위핑한다.

end 점 : 현재까지 심은 꽃의 마지막 좌표

maxE 점 : end 점과 새로운 선분을 이을 때 가장 멀리 갈 수 있는 끝점 좌표

maxE 보다 새로운 선분의 시작 점(nowS)이 크다면 선분은 중간에 끊어지게 되므로 카운트 0이 되고 종료한다.(시작점에 대해 정렬되어 있으므로)

아니라면 현재 선분과 새로운 선분을 이을 수 있다. 다음과 같이 진행한다.

- end 보다 새로운 선분의 시작 점(nowS)이 크다면 -> 새로운 선분을 이어야 한다.(카운트 1증가)

- 새로운 선분의 끝 점(nowE)과 maxE를 비교해 maxE를 계속 갱신한다.

- maxE 가 11월 30일을 넘어가게 되면 그 선분과 바로 이으면 되므로 카운트 1을 증가시키고 종료한다.

(끝점에 대해 내림차순이므로 다음 선분은 더 짧다)

여러 선들이 주어지는데, 단 하나의 선만 제거했을 때 선들이 겹치는 길이를 최대화하는 문제이다.

아이디어는 다음과 같다.

fixLine = 두 개 이상의 선들이 겹치는 구간으로, 선 하나를 제거해도 여전히 유효하므로 답에 무조건 더해져야 한다.

line = 단 하나의 선만이 가지는 구간이다. 여러개의 line 중 가장 작은 line을 선택해 제거해야 최대의 답을 얻을 수 있다.(코드에선 구간의 길이만 오름차순으로 저장했다)

시작점, 끝 점 모두 내림차순 정렬하고 스위핑 알고리즘을 사용해 모든 구간에 대해 fixLine 구간과 line 구간을 구해주었다.

fixLine 구간은 서로 겹칠 수 있으므로 다시 스위핑 알고리즘을 사용해 겹치는 총 길이를 구했다.