11004번 - K번째 수
무슨 방법을 해도 안되길래
스택에 k개까지만 넣고, top값과 비교해서 입력값이 더 작으면 pop하고 push하고 스택만 정렬...
반복해서 바로 스택 top-1을 출력해줬는데
이조차 TLE가 뜹니다 ㅠㅠㅠㅠ
컴파일러 바뀌었다고 들었는데 그 때문에 시간초과가 뜨는건지... 아니면 제 방법도 한참 느린건지... 모르겠습니다 ㅠㅠ
제 코드가 안 된다면 이유라도 알려주세용 ㅠ.ㅠ
아마 이게 라이브러리 소팅을 사용해도 빠듯하게 될 것 같은데 입력받는 시간이 오래 걸릴 것 같네요.
k개만 정렬하신다고했는데, 최악의 경우 n - k번 k개를 정렬겠네요.
그러면 시간복잡도가 O((n - k) * k*ln(k))라서 TLE일 수 밖에 없겠네요...
한번 퀵정렬 알고리즘을 응용해보세요.
아 코드를 보니 O(nk*lg(k))이겠네요.
O(n)보다는 작게 나와야 맞을수있어요.
다시보니 시간이 늘어서 O(k*lg(k))도 가능하네요ㅋㅋㅋ
빠른 입출력과 nth_element()를 이용하시면 PASS가능 하세요
max heap을 잘 쓰면 O(nlgk)에도 될 것 같아요
모두들 감사합니다...!!
조언해주신대로 다시 해볼게요!
maxheap으로 구현해본결과 시간초과 뜨네요..
댓글을 작성하려면 로그인해야 합니다.
dreammusic23 8년 전
무슨 방법을 해도 안되길래
스택에 k개까지만 넣고, top값과 비교해서 입력값이 더 작으면 pop하고 push하고 스택만 정렬...
반복해서 바로 스택 top-1을 출력해줬는데
이조차 TLE가 뜹니다 ㅠㅠㅠㅠ
컴파일러 바뀌었다고 들었는데 그 때문에 시간초과가 뜨는건지... 아니면 제 방법도 한참 느린건지... 모르겠습니다 ㅠㅠ
제 코드가 안 된다면 이유라도 알려주세용 ㅠ.ㅠ