집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 d로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하고자 한다.
가장 간단한 방법으로는 특정 지점을 가지고 모든 사람들을 순회하며 검사하는 방식이 떠오른다. 하지만 그렇게 하기엔 철로의 범위가 너무 넓다. 우선 사람을 정렬해보고, 정렬된 결과를 이용해서 어떻게든 해볼 수 없을까?
직접 손으로 한다면 아래와 같은 느낌으로 해결이 가능할 것 같다.
우선순위 큐를 이용하면 이 아이디어를 효율적으로 구현 할 수 있다.
사람들을 2가지 기준으로 정렬한다면, 문제를 간단하게 해결 할 수 있다.
우선, 종료지점을 기준으로 오름차순 정렬 시킨다.
위의 기준으로 정렬된 사람들을, 한 명씩 다른 컨테이너로 옮긴다
이때 삽입과 동시에 시작 지점을 기준으로 오름차순 정렬시킨다.
만약 처음 정렬을 시작 지점을 기준으로 정렬했다면, 다른 컨테이너로 옮길 때의 정렬 기준과 오름, 내림차순이 바뀌어야 한다.
우선 구현이 간단한 위의 기준으로 설명을 진행해본다.
종료지점 기준 오름차순 정렬 이므로, (10, 20)인 사람이 가장 먼저 우선순위 큐에 들어온다.
여기서 "현재 : 20" 은 (10, 20)인 사람의 종료지점이며 동시에 현재 철도의 오른쪽 끝 구간을 의미하게 된다.
사람들이 종료지점을 기준으로 오름차순 정렬돼있기 때문에, 단계가 진행되어도 이미 큐 안에 들어와 있는 사람들의 종료 지점은 항상 새로 들어오는 사람의 종료 지점 이하의 값을 갖는다.
우리는 새로운 사람이 들어왔을 때, 즉 철도의 종료지점이 갱신되었을 때, 큐 안에서 해당 철도의 혜택을 못 받는 사람들을 쫓아낼 것이다.
현재는 (10, 20)인 사람 1명뿐이다.
철도는 현재 위치 - 철도의 길이부터 시작한다. (철도의 시작 = 철도의 끝 - 철도의 길이) 즉 현재 철도는 -10 ~ 20 구간을 지난다. 다행히 방금 들어온 사람은 쫓겨나지 않았다.
다음 사람이다. 철도의 끝은 30으로 갱신되었다.
이번에도 큐에서 아무도 쫓겨나지 않았다.
이때 큐의 맨 앞 항목만 비교하는 이유는 우선순위 큐의 정렬 기준을 "시작 지점의 오름 차순"으로 정렬했기 때문이다. 즉 현재 큐는 시작 지점이 작을수록 앞에 있게 되고, 맨 앞 항목보다 더 앞에 있을 수 있는 사람은 없다.
큐에 있는 모든 값이 10 이하 (우선순위 큐의 정렬에 의한 확정) 30 이상 (최초 사람 정렬에 의한 확정) 범위에 있음을 전체 탐색 없이 알 수 있다.
다음 사람이 들어와 철도의 끝 지점이 갱신되었다.
그런데 이번에 새로 온 사람의 시작 지점이 5 이기 때문에 우선순위 큐의 동작에 의해 아래와 같이 정렬된다.
현재 큐 안에 있는 모든 사람은 5~40 범위 내에 존재하게 된다.
큐의 맨 앞 값에 대하여 철도의 혜택을 받을 수 있는지 체크해보니 철도의 영역에서 벗어난다. 현재 철도는 10에서 40까지 설치되어있다.
그러므로 방금 온 손님은 바로 퇴장하게 된다. 새롭게 맨 앞이 된 (10, 20)은 현재의 철도 혜택을 받을 수 있다.
이러한 방식으로 계속 탐색을 진행해간다.
위의 설명을 이미지로 나타내면 다음과 같다.
이러한 유형의 문제는 다른 컨테이너에 삽입과 동시에 어떠한 행위를 시키는 테크닉이 필요한 문제이다.
여기서는 간단한 우선순위 큐를 사용했지만, 문제에 따라 우선순위 큐 (=힙) 이 아닌 AVL 트리나 RB 트리가 필요할 수도 있다.
예를 들어 새로운 컨테이너로 이동 후, 10번째 값을 확인해야 한다면 우선순위 큐의 특징으로는 한계가 있다.
하지만 그런 복합적인 문제는 조금 미래로 넘기고 우선은 우선순위 큐를 이용한 문제에 익숙해져 보자.
