h00201   2년 전

퀵정렬을 이용해서 풀려고 시도했는데 시간초과는 커녕 계속 틀렸다는 답만 나오네요..


물론 푼 것도 그렇게 잘 푼 것은 아니지만..


혹시 반례가 있는지 찾아주실 분 계신가요?

djm03178   2년 전

첫째로, %d는 int형을 출력하는 포맷이므로 sum을 출력하기에 적절하지 않습니다. %lld를 써야 합니다.

둘째로, 매번 정렬하고 원래대로 돌려놓는 이 방식은 큰 케이스에서 필시 시간 초과가 납니다. 간단히 시간 복잡도를 생각해보면 k개를 정렬(O(klgk))하고 복사(O(k))하는 작업을 O(n)번 반복해야 하니 O(nklgk) 정도로, 170억 가량이 되어 불가능합니다.

h00201   2년 전

흠.. 아무리 생각해봐도 최소 O(NK)까지밖에 생각이 안나네요.. 다른 방법에 대한 힌트가 혹시 있을까요?

djm03178   2년 전

다른 방법도 있는 듯하지만 제가 사용한 건 가운데 값을 항상 상수 시간에 뽑고 빠져나갈 것을 빼고 들어올 것을 넣는 데에 각각 lg k 시간이 걸리는 알고리즘이었습니다.

h00201   2년 전

상수시간에 뽑는다는건 첫 입력 때 중앙값을 이미 정리한다는 의미인가요?

그렇다면 아예 다른 방법을 생각해야 할 것 같은데.. segment tree같은걸 봐도 도통 이해가 안되네요..


그 외엔 아예 감도 안잡히고... 흑흑

djm03178   2년 전

참고로 테스트 케이스가 약해서인지는 모르겠지만 제가 예전에 매우 최적화된 O(nk) 코드로 988ms에 통과한 적이 있기는 합니다. 하지만 의도된 대로라면 확실히 난이도가 높은 문제라고 생각합니다.

h00201   2년 전

다른 글들을 검색하니 테스트 케이스가 약하다고 하시네요 대부분.. nk로 짜봤는데 시간이 오버되는걸 봐선 제가 짠 nk 자체도 최적화가 안 된 것 같네요 -_-;;

계속해서 빠른 답변 감사합니다. klgk 방법을 찾아봐야 할 것 같아요. 아마 군인이라 쉽진 않겠지만;

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