travis97   4년 전

O(n)time 걸리면 안된다고 같은 문제 게시판에서 본 것 같은데, 

그거 어떻게 알 수 있나요?

그리고 왜 시간초과 됐는지 어떤 방향으로 수정하면 좋을지 부탁드립니다. xcode에서 결과는 같게 나옵니다. 

ckdgus2482   4년 전

O(n)이 아니라 I나 D 작업 한번 하는 것에 대한 시간복잡도 성능이 O(k)이면 안된다는 얘기일 것입니다.

그렇게 되면 전체 시간복잡도가 O(k^2)인데 k가 최대 100만이므로 시간초과입니다.

I, D 작업을 O(lg(k))에 처리할 수 있으면 전체 시간복잡도는 O(k lg(k))가 되는데 k에 100만을 대입했을 때 대략 2천만 정도이므로 6초면 충분히 처리될 수 있습니다.

실제 우선순위 큐 자료구조에서 데이터 삽입이나, 최대 또는 최소값의 룩업에 O(lgN)의 시간복잡도를 갖는데 이 문제에서도 그 정도의 시간복잡도 성능을 요구합니다.

STL 중에 multiset이라는 것이 있는데 균형잡힌 이진트리로 전체 데이터를 정렬한 채로 관리해주며, 모든 위치에 대해 삽입 및 삭제가 로그시간복잡도를 가지기 때문에 이것을 사용하면 쉽게 풀리는 문제입니다.

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