goodinet   4년 전

quick selction도 짜보고 이를  11004번 k번 째 수에 제출하니 시간이 똑같게 나와서 nth_element를 사용하기로 하였습니다.

알고리즘 자체는,

mid배열에 K개 만큼 입력을 받고, 다음 입력 때 마다, 뺄 수를 빼고, 그 자리에 입력한 값을 넣어 중앙값을 구하게 합니다.

하고 싶었던 시간 복잡도는 NK였으나 뺄 수를 찾는 과정에서 시간이 더 들어서 시간초과가 될 수도 있겠다...헀습니다만 이렇게 풀면 안되는건가요?


그리고 너무너무 궁금한 부분 중 하나는

제가 이 코드가 얼마나 시간이 초과했는 지 궁금하여서 i가 도는 for문에

if(i==249999) printf("asdfasdf\n"); 이렇게 적어놓으면 시간초과가 나지 않고 틀렸습니다! 가 나오더라구요....

아니 그럼 돌긴 또 거의 도는 건지 백준 채점이 어느정도 답을 구하고 시간초과를 따지는 건지 모르겠습니다ㅠㅠㅠ 미쳐버리겠네요


제가 이 문제를 풀려면 다른 알고리즘이 필요한 지, 궁금합니다ㅜ

jseo   4년 전

10^8개의 연산을 보통 1초라고 보니, O(NK)로는 시간 초과를 피하기는 어렵겠죠. 

이 문제는 이진 검색 트리 두개로 풀 수 있습니다. (물론 직접 구현 할 필요는 없고 STL에서 적절한 자료구조 찾아서 쓰면 됩니다. 저같은 경우는 multiset 두개 썼습니다)

goodinet   4년 전

ㅜㅜㅜㅜ 지금 굉장히 굉장히 고민해보고 또 다른 방법으로 짜봤지만 역시나 5%에서 시간초과가 나는군요ㅠㅠㅠ

어느부분에서 시간을 줄이려고 하려면 되는 지 알 수 있을까요?..ㅠㅠ

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