jh05013   3년 전

단계별로 풀어보기로 이 문제를 접하는 분들은 모든 중앙값을 "부분배열을 뽑아내고, 정렬한 다음 가운데 원소를 얻어내는" 방법으로 푸실 것입니다. 이렇게 하면 시간초과가 납니다. 심지어 퀵셀렉이나 O(K)짜리 정렬 알고리즘을 써도 시간초과가 나오는 것으로 알고 있습니다.

단순히 이름이 "중앙값 측정"이라는 이유로 정렬하기 단계에 있는 건 아닌지 확인 부탁드립니다.

djm03178   3년 전

처음에 K개를 정렬하고 들어가는 알고리즘도 있긴 하지만 그게 핵심은 아닐 거고... 제 코드 하나 읽으셨듯이 O(NK)짜리가 가까스로 통과될 수도 있는데 이건 데이터가 약해서인 거 같으니 확실히 이 문제가 정렬이 중심이 되는 건 아닌 것 같습니다.

startlink   3년 전

정렬하기에서 삭제했습니다.

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