선분이 겹치는 구간의 길이를 찾는 문제. 그런데 인덱스를 사용하지 않는

Q. lines = [[1, 3], [2, 4], [3, 5]]와 같이, 선분의 시작과 끝 좌표로 이루어진 배열의 배열이 주어진다.

두개 이상의 선분이 겹치는 길이를 구해보자.

 

처음의 계획

1. lines를 순회하면서 [자연수, 자연수 + 1]의 구간을 Map에 저장한다.

2. Map을 순회하면서 value가 2이면 answer을 1만큼 증가시킨다.

시간 복잡도 = O(\(N^2\)) (N: lines를 통해 주어지는 구간의 전체 길이)

 

N이 크지 않아서 이 방법도 좋았는데, 구간의 처음과 끝을 아는 상태에서 일일이 길이가 1인 구간으로 나눠서 맵에 추가한다는게 번거로웠다. 굳이 인덱스를 다루고 싶지 않았다.

 

그래서 둘째 계획으로 변경했다.

1. 구간 전체를 순회하면서 [자연수, 자연수 + 1]의 구간을 만든다.

2. lines를 순회하면서 해당 구간을 포함하는 구간을 찾고, 그 구간이 2개 이상이면 answer을 1만큼 증가시킨다.

시간 복잡도 = O(\(N^2\))

 

시간 복잡도는 작아지지 않았지만 lines의 요소를 순회하면서 인덱스를 다루지 않는 것으로 만족했다.

 

그렇게 정답을 제출하고 다른 사람들의 풀이를 보던 중 인덱스를 다루지 않는 방법을 찾았다.

심지어 시간복잡도도 O(\(NlogN\))으로 더 작았다.

 

1. lines를 순회하면서 구간의 시작점과 끝점을 PriorityQueue에 추가한다.

2. PriorityQueue가 빌 때까지 순회하면서 구간의 시작점을 만나면 thick을 1만큼 증가시키고, 끝점을 만나면 1만큼 감소시킨다. 그리고 thick > 1이라면 answer을 curr - prev만큼 증가시킨다.