[문제]
생물체의 특정 염색체를 Next Generation Sequencing(NGS) 기기를 이용하면 해당 염색체 전체를 작은 조각으로 잘라서 읽을 수 있다. 이 서열화(Sequencing) 단계는 분자생물학, 생물정보학 연구에서 가장 중요한 작업이다. 이때 NGS 기기를 통해서 읽은 전체 DNA 서열의 조각을 read라고 부른다. DNA로 이루어진 염색체의 길이는 보통 수백 메가바이트의 크기이므로 한 번의 NGS 실험으로 생산되는 리드(read)는 수억에서 수십억 개에 이를 정도로 매우 많다.
실제 {모기, 고릴라, 개, 사람}의 몇 염색체에서 추출된 read sequence가 주어진다. read 서열은 { a, g, t, c } 4개의 염기를 나타내는 소문자들로 구성되어 있다.
입력으로 받은 read의 개수를 N이라고 하자. 여러분은 N개의 read 집합을 사전식(lexicographic)으로 정렬했을 때
$\left \lfloor N/5 \right \rfloor$, $\left \lfloor 2N/5 \right \rfloor$, $\left \lfloor 3N/5 \right \rfloor$, $\left \lfloor 4N/5 \right \rfloor$번째에 해당하는 read, 즉 정렬된 read를 5개 구간으로 나누었을 때 순서로 볼 때 20%, 40%, 60%, 80% 순서에 있는 4개의 read를 찾아서 모두 순서대로 출력해야 한다. 위에서 표시된 floor 함수 $\left \lfloor x \right \rfloor$는 $x$를 넘지 않는 최대 정수를 의미한다.
예를 들어 $\left \lfloor 345.678 \right \rfloor = 345$, $\left \lfloor 45 \right \rfloor = 45$로 계산된다. 만일 N=12345라고 한다면 찾아야 할 4개의 순서는 정렬 후 2469, 4938, 7407, 9876번째이다. 이 경우 여러분은 정렬된 read의 순서가 0번부터 시작할 때, 2469, 4938, 7407, 9876번째에 해당하는 read를 각각 찾아서 출력해야 한다.
[입출력]
입력파일은 read.inp이고 한 줄에 하나씩의 read가 있으며 그 길이는 각각 다를 수 있다. 각 read의 최대 길이는 1000으로 매우 긴 read가 들어올 수도 있다. 입력 read의 수는 최소 천(1000) 개, 최대 20만 (200,000)개이다. 여러분은 전체 입력 read 갯수가 N개일 때 정렬순서로 볼 때 $\left \lfloor N/5 \right \rfloor$, $\left \lfloor 2N/5 \right \rfloor$, $\left \lfloor 3N/5 \right \rfloor$, $\left \lfloor 4N/5 \right \rfloor$순서에 해당하는 read를 찾아서 출력해야 한다.
[풀이]O($klog_5{n}$) $k$는 read의 최대 길이
위 링크의 문제는 mergesortTree를 이용하는 문제다. 매번 mergesort를 할 수는 없으니 mergesort과정을 tree로 저장하여 각 query를 $logn$에 해결하는 문제다.
반면 이번 과제는 radixsort를 이용해야하며, query가 4번으로 고정되어 있다. 따라서, sort과정을 tree로 저장할 필요가 없으며, 각 쿼리마다 radixsort를 해나가며 필요 없는 부분은 버려가면서 탐색해나가면 해결이 가능하다.
여기서 필요 없는 부분이란, $9$번째 원소를 찾아야할 때 $a$로 시작하는 string의 크기가 5이면 $a$로 시작하는 string들은 radixsort할 필요가 없다. $c$로 시작하는 원소의 크기가 3인 경우도 마찬가지로 $5 + 3 \leq 9$이므로 탐색할 필요가 없으며, $g$의 크기가 1이상인 경우 $g$에서 부터 다시 radixsort를 하면 되므로 매번 탐색의 크기가 $1/4$만큼. 아니, 빈 문자까지 추가해주면 $1/5$만큼 줄어들게 된다.
앞의 설명에서 알 수 있듯이, 기존의 radixsort는 run을 뒤에서부터 정렬해나가는 것이 구현상 훨씬 유리하기때문에 뒤에서부터 정렬해나갔지만, 그렇게 하게 될 경우 이번 문제를 해결하지 못 한다.
앞에서 부터 sort해나가며 index를 증가시켜가며 각 run에 대해 재귀적으로 탐색해나가야한다.
설명을 보는 것 보다 코드를 보는게 훨씬 이해하기 쉬울 것이므로 아래 코드를 참고하기 바란다.
참고로, query가 4번이라해서 4번 radixsort해줄 필요가 없다. query set 4개 통채로 함수로 넘겨서 적절히 처리해주면 4개의 쿼리를 1번의 radixsort로 처리가 가능하다.
구현이 약간 꼬여서 복잡하지만, 두 코드를 비교해보면서 조금만 생각해보면 왜 1번의 radixsort로 4번의 query를 처리 가능한지 알 수 있을 것이다.
[코드] - 4번의 radixsort
[코드] - 1번의 radixsort
