wbluke
commented
5 years ago [My Point]
- Treap이라는 처음보는 자료구조에 그냥 책보고 하나씩 구현해보았다. 랜덤함수로 priority를 정하다니 신기하네. Tree와 Heap을 합쳐서 Treap이란다.
[Idea Point]
- 보통의 BST는 라이브러리에 꽤 균형잡힌 Red-Black Tree로 구현되어 있다. 다만, k번째 원소가 찾고 싶다던가, 어떤 원소보다 작은 원소들의 수 같은 라이브러리에 없는 기능들이 필요할 때 직접 구현해야만 한다. 그 때 자주 쓰이는 자료구조가 Treap이다.
- 뒤에서부터 숫자를 읽는다. 숫자의 의미는 해당 자리의 정답숫자보다 큰 숫자들이 앞 쪽에 있다는 것이고, 이를 알기 위해서는 어떤 집합에서 k번째 원소를 빠르게 찾는 것이 필요하다. 하나를 찾고나면 그 숫자를 후보군에서 제외한 뒤 다음 숫자로 넘어가면 된다. Treap을 굳이 사용하지 않아도 되지만, 매우 빠른 시간의 단축을 가져올 수 있다.
https://algospot.com/judge/problem/read/INSERTION