dustn9401   4년 전

일단 1부터 n까지의 숫자가 중복없이 나오니까 배열을 포인터처럼 사용해서 트리를 만들었습니다.

l에는 각 노드의 왼쪽 노드번호, r에는 오른쪽을 저장합니다.

level에는 각 노드의 레벨을 저장합니다.

tree에는 삽입된 모든 원소를 정렬된 상태로 저장합니다.

현재 삽입될 숫자인 num에 대해 lower_bound를 사용하여 tree 내에서의 위치를 찾습니다.

찾은 위치는 low라는 iterator에 저장합니다.

low - 1은 num 미만의 가장 큰 수를 가리키고, low는 num 초과의 가장 작은 수를 가리키므로

num보다 작은 수가 없는 경우, num보다 큰 수가 없는 경우, 그 외의 경우로 나누어서 코드를 작성했습니다.


예제는 잘 나오는데 시간초과가 어디서 나는지 모르겠습니다. lower_bound를 사용한 것이 조금 의심스럽긴 한데 그래도 n*logn의 시간복잡도가 아닌가요?

chogahui05   4년 전

http://www.cplusplus.com/refer...

Linear on the number of elements inserted (copy/move construction) plus the number of elements after position (moving).


다른 건 볼 필요 없고요.

300000

30만 299999 299998 ... 1

이런 TC를 돌려보세요. 어떻게 나올까요?

dustn9401   4년 전

아하 삽입할 때에 하나하나 뒤로 밀어내는데에 시간이 많이 걸리겠군요... 리스트 같은걸 써야겠네요 감사합니다!

dustn9401   4년 전

흑흑...

djm03178   4년 전

ㅎㅎ 저는 최악의 경우 n log n 시간이 되는 알고리즘을 짰는데, 어떤 분들은 linear 시간에 되는 것들도 만드시더라고요. 시간상으로는 저처럼 짜도 매우 빠른 편에 끝나기는 하는데, 코드가 더러워서 추천해드리기는 좀 어렵겠네요 ㅠ

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