BOJ 19089번 - 파일 합치기 4

19089번: 파일 합치기 4

Garsia-Wachs algorithm 또는 Hu-Tucker algorithm으로 풀이할 수 있다.

나는 Garsia-Wachs algorithm으로 풀이하였다.

 

원본 논문보다는 이 논문을 보는 것을 권장한다.

알고리즘 자체는 간단한데 다음 두 단계를 N - 1번 반복하면 된다.

(i) Locate the rightmost R.M. pair of entries. Let that be p_i-1, p_i.

(ii) Next locate the first entry to the right of p_i that is greater than or equal to p_i-1 + p_i.

증명은 매우 어려우므로 생략한다.

 

O(N^2) 구현은 매우 쉽지만 이를 O(N log N)으로 구현하는 것이 관건이다.

현재 대부분의 AC 코드는 Splay Tree를 이용하는 것으로 보인다.

하지만 알고리즘의 동작을 잘 관찰해보면 Splay Tree 없이 구현할 수 있다.

TAOCP에 관련 내용이 있는데 읽어 보면 도움이 될 수도 있다.

 

나는 다음과 같은 네 개의 자료 구조를 이용하여 구현하였다.

• list<iii>
• vector<vector<list<iii>::iterator>>
• priority_queue<iii>
• map<int, int>

아이디어를 간단히 설명하자면 다음과 같다.

• 배열의 각 원소는 doubly linked list로 관리하며 각 원소마다 가상의 인덱스 (i, j)를 부여한다.
• 각 원소를 상수 시간에 접근하기 위하여 모든 가상의 인덱스에 대하여 iterator를 관리한다.
• 삭제할 pair를 찾기 위하여 priority_queue<iii>를 이용한다.
• 삽입할 인덱스를 찾기 위하여 map<int, int>를 이용한다.

상수가 커서 그런지 속도는 Splay Tree 구현보다 느리다.

 

끝