kthng   7년 전

문제를 풀어갈 과정은 찾았는데... 자료구조에서 막히네요


1 2 3 4 5 6 7 8 9 10 11 12 에서

앞에 4개명의 작거나 같은 사람이 있다고 한다면, 4번째 숫자인 5를 제외한

1 2 3 4 6 7 8 9 10 11 12를 유지하고 5번째 작은 숫자인 145를 제외해줍니다.

마찬가지 방법으로

10번째인 11을 제외한 1 2 3 4 6 7 8 9 10 12 숫자는 172

7번째인 8을 제외한 1 2 3 4 6 7 9 10 12 숫자는 163

5번째인 6을 제외한 1 2 3 4 7 9 10 12 숫자는 155

8번째인 12를 제외한 1 2 3 4 7 9 10 숫자는 182

7번째인 10을 제외한 1 2 3 4 7 9 숫자는 167

....

입력으로 주어진 0 1 0 0 3 2 6 7 4 6 9 4 에서

뒤에서부터 읽으면 4 9 6 4 7 6 2 3 0 0 1 0 가 각각 자신의 앞에 있는 자신보다 키가 작거나 같은사람이고, 

그렇다면 앞에있는 사람만 보았을 때 자신의 키순번이 5 10 7 5 8 7 3 4 1 1 2 1 이기때문에 이 방법으로 구현하면 답은 나올 것 같아요.


이런식으로 초기 n개의 정렬된 자료구조에서 k번째 숫자를 빼는 것을 반복하는 것으로 구현하려고 하는데... 배열로 해도 시간복잡도는 n^2이고, list도 n^2,... 응용한다고 해서 union find로 해보려고 했는데 이것도 결국 n^2,.. 펜윅트리로 해보려고했는데도 이건 올바른 접근법이 아니더군요...

n개의 정렬된 구조에서 k번째 숫자를 logn time 이하로 빼내는 자료구조가 있을까요?

아니면 이 문제 해법 검색해도 안나오던데... 유사한 문제 해법이 있으면 알려주시면 감사하겠습니다...^^

portableangel   7년 전

방법이야 많을 수 있지만, 그 중 한 가지로 합 세그먼트 트리를 이용하면 쉽게 가능합니다.

각 숫자를 리프로 하여, 숫자가 있을 경우 1, 없을 경우 0을 저장한 뒤

시작점부터 계산하여 합이 K가 되는 가장 가까운 지점을 찾게 되면 해당 노드엔 항상 1이 저장되어 있고, 해당 노드의 번호가 바로 K번째 수입니다.

숫자를 사용한 뒤에는 0으로 업데이트시켜주시면 됩니다.

yukariko   7년 전

말씀하신 자료구조는 이진 탐색 트리에서 k번째 숫자를 찾는 코드를 추가하면 됩니다.

물론 stl의 map이나 set에선 이를 지원하지 않기 때문에

레드블랙트리를 직접 구현하거나 treap이라는 대체수단도 있긴합니다.

저는 treap으로 해결했습니다만 다른분들은 세그먼트 트리로도 해결하신것 같네요

kthng   7년 전

정말 빠른 답변 고맙습니다~!!!!

합이 K가 되는 가장 가까운 지점을 찾는데도 시간복잡도는 nlogn 아닌가요..?? 아 맞다 이분탐색....ㅎㅎㅎㅎㅎ

고맙습니다..ㅜㅜ

kthng   7년 전

yukariko 님 고맙습니다.

treap.. 공부해봐야겠네요

kthng   7년 전

펜윅+이분탐색으로 해결했어요..^^

댓글을 작성하려면 로그인해야 합니다.