dgmsky   2년 전

현재 quick selection으로 짜고 있으나, 틀렸습니다가 나오는 상황입니다.


quick selection이 quick sort 변형인 것으로 알고 있어서, partition2 함수처럼 짰다가, 메모리 초과가 나오길래 partition 함수형태로 짰는데도 틀렸다고 나오네요;;

느 부분에 수정이 들어가야 하는지 감을 못잡겠습니다...


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



daniel00   2년 전

이 문제는 아래 문제와 완전히 동일한 문제입니다.

https://www.acmicpc.net/proble...

최초 배열에서 맨앞데이터가 삭제되고 맨끝에 새로운 데이터가 삽입되므로 

(1)펜윅트리를 구현해서 부분배열이 변경될때 마다 매번 위의 2포인트씩만 update()해주고 , (O(logN))

바이너리서치로(O(logN)) 중앙값을 찾아내는 방법으로 풀어보시면 될 겁니다.

펜윅트리에는 배열의 값이 출현하는 빈도수를 저장한다는점에 유의하세요.

고민하고계신 퀵셀렉트로 풀면 타임아웃에 걸릴듯합니다.

풀이에 성공하시길 바라겠습니다.


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