jaywonchung   2년 전

처음엔 deterministic selection을 구현해서 풀다가 도저히 시간초과를 피할 수가 없어 다른 방법을 생각해보게 되었습니다.

input은 0~65535 사이에서 들어오므로, unsigned short count[65536];으로 선언한 array에 들어온 숫자의 개수를 기록합니다. 즉, n이 들어오면 count[n]++;를 해줍니다.

count를 보고 count[i]를 쭉 더하다가 더한 값이 (k+1)/2 이상이 되면 i-1이 중앙값이 되게 됩니다.

그리고 2%에서 시간초과가 뜹니다.....

count array를 쭉 진행하면서 값을 더하는 과정이 너무 오래 걸리는걸까요? 아니면 혹시 count에서 index를 찾아가는 게 오래 걸리나요?

고수님들의 조언을 구합니다ㅠㅠ


koosaga   2년 전

65536*N (getmid = 최악 65536번 정도 연산) 이니 시간초과는 당연히 나야하고요

count 배열은 N번만 건드리니 문제가 없습니다. 

koosaga   2년 전

시간 복잡도 개념에 대해서 공부하시는 것을 추천드립니다. 

chogahui05   2년 전

일단 규칙을 먼저 찾아보시고 

그게 안되신다면 게시판 몇 번 더 정주행 해 봅시다.

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