스위핑/구간 트리. [5419]

[1. 문제 설명]

북서풍으로 인해 현재 위치에서 동쪽과 남쪽 사이의 위치로만 이동 할 수 있을 때

북서풍을 타고 항해 할 수 있는 섬의 쌍의 수를 구하도록 한다.

---

[2. 풀이 접근]

먼저 전체 좌표를 y 의 내림차순으로 정렬한다.

그러면 이전 좌표는 신경쓰지 않아도 된다.

현재 위치에서 남쪽으로만 갈 수 있지, 북쪽으로는 갈 수 없기 때문이다.

 

이 상태에서 x 를 처리하도록 한다.

기본적인 생각은 x 의 발생 빈도를 구간 트리로 처리하는 것이다.

 

아래 그림에서 2번 좌표는 최소 31 번까지의 좌표로 이동 할 수 없다.

남쪽으로는 갈 수 있지만, 서쪽으로 이동 하기 때문이다.

 

즉, 남은 구간에서 현재 x 보다 큰 것의 개수만 구할 수 있다면,

현재 섬에서 동남쪽으로 이동 할 수 있는 점의 개수를 찾을 수 있다.

그러나 x 의 범위가 -10억 ~ 10억 사이이므로

이 범위를 표현 할 수 가 없다.

 

여기서 좌표 압축을 적용 할 수 있다.

x 라는 좌표가 표현하는 범위는 매우 넓지만,

x 좌표의 개수는 이보다 훨씬 적은 75,000 개 이므로

x 를 오름차순으로 정렬하여 x 를 다시 [0, 75,000] 사이의 값으로 다시 매핑하는 것이다.

 

이렇게 하여 구간에서 x 의 발생 빈도를 nlogn 으로 알 수 있게 된다.

 

마지막으로 처리 할 부분은 다음 좌표로 넘어가기 전에

x 의 발생 빈도를 표현한 구간트리에서 현재 좌표의 x 를 제거해야 한다는 것이다.

---

[3. 코드]