dreammusic23   8년 전

무슨 방법을 해도 안되길래

스택에 k개까지만 넣고, top값과 비교해서 입력값이 더 작으면 pop하고 push하고 스택만 정렬...

반복해서 바로 스택 top-1을 출력해줬는데

이조차 TLE가 뜹니다 ㅠㅠㅠㅠ


컴파일러 바뀌었다고 들었는데 그 때문에 시간초과가 뜨는건지... 아니면 제 방법도 한참 느린건지... 모르겠습니다 ㅠㅠ

제 코드가 안 된다면 이유라도 알려주세용 ㅠ.ㅠ

indioindio   8년 전

아마 이게 라이브러리 소팅을 사용해도 빠듯하게 될 것 같은데 입력받는 시간이 오래 걸릴 것 같네요.


isac322   8년 전

k개만 정렬하신다고했는데, 최악의 경우 n - k번 k개를 정렬겠네요.

그러면 시간복잡도가 O((n - k) * k*ln(k))라서 TLE일 수 밖에 없겠네요...


한번 퀵정렬 알고리즘을 응용해보세요.

isac322   8년 전

아 코드를 보니 O(nk*lg(k))이겠네요.

O(n)보다는 작게 나와야 맞을수있어요.

isac322   8년 전

다시보니 시간이 늘어서 O(k*lg(k))도 가능하네요ㅋㅋㅋ

baactree   8년 전

빠른 입출력과 nth_element()를 이용하시면 PASS가능 하세요

2e718   8년 전

max heap을 잘 쓰면 O(nlgk)에도 될 것 같아요

dreammusic23   8년 전

모두들 감사합니다...!!

조언해주신대로 다시 해볼게요!

x21999   7년 전

maxheap으로 구현해본결과 시간초과 뜨네요..

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