hoon941209   2년 전

계속 시간초과가 나는데 이유를 모르곘어요..ㅠ


djm03178   2년 전

힙을 이런 식으로 구현한 건 처음 봅니다. 보통 힙에서는 위아래로만 이동을 하지, 연산 중 idx-- 같은 건 하지 않는데, 이런 방식으로 짜는 코드를 어디서 보신 건가요, 아니면 직접 생각해서 구현하신 건가요?

hoon941209   2년 전

직접 생각해서 구현해봤습니다.

djm03178   2년 전

그렇다면 코드에 설명이 없다는 점이 더욱 아쉽군요. 나만의 아이디어를 생각한 거라면, 다른 사람에게도 그 아이디어를 설명하고 왜 그게 시간 안에 돌아야 한다고 생각하는지도 알려주는 게 좋다고 생각하는데요.

단순하게 생각해 봐도, N부터 1까지의 수에 대해서 idx가 각 수에 대해 1이 될 때까지 감소를 시키니 O(N^2) 이상이 되는 건 확실한 데다가 (물론 정확히는 2로 나눈 곳부터 시작하기는 하지만, 그래봐야 상수배입니다), 중간에 swap이 일어난다면 더 많이 루프를 돌 수도 있겠네요.

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