hippohmh   2년 전

우선 제가 알고리즘이나 자료구조 지식이 부족하여 quick selection으로 짰음을 알려드립니다.

VC2015에서 돌릴 때는 잘 돌아가는 것 같은데 제출하면 틀렸다고 뜨네요.

어느 부분이 틀렸나요?

quick selectin으로 짜면 무조건 시간초과가 나오나요?

djm03178   2년 전

quick selection이 기존의 배열 자체를 변경하기 때문에 이 방법으로는 원소들의 순서가 망가져서 잘 안 될 것 같습니다. 굳이 한다면 매번 범위만큼 다른 배열에 복사해두고 찾을 수는 있겠지만, 제가 988ms에 통과시켰던 조금 무식한(?) 방법보다 느릴 것 같아서, 아마도 어렵지 않나 생각합니다.

djm03178   2년 전

마침 아이디어가 하나 떠올라서 다시 풀어서 56ms에 통과했네요. C나 C++로 O(nk)시간에 최대한 최적화해서 가까스로 AC를 띄우는 것도 가능은 하지만, 잘 만들면 O(n lg k) 시간에 해결하는 게 가능하네요. 그쪽을 잘 생각해보시면 좋을 듯합니다.

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