두 개의 우선순위 큐를 써서 중앙값 찾기

어떤 숫자들의 입력이 계~속 주어진다. 들어온 입력들에 대해서 중앙값을 계속 반환해야 한다. 자 그럼 이걸 어떻게 해볼까? 들어온 입력을 계속 push 하고 정렬을 한다?-> N번 동안 N 크기의 배열을 정렬하므로 N^2logN  . 따라서 시간 초과가 될 수 밖에 없다. 우리가 원하는 건 "중앙값"이다. 구체적으로 전체가 어떻게 정렬되어 있는지는 관심이 없다.중앙값을 T 라고 했을 때, T는 정렬된 List 에서 가운데에 위치해야 한다. 하지만, 정렬을 다해주면 시간 초과. 그래서 정답 T에 대해 배열을 다음과 같이 나눠보자.1. 무조건 작은 쪽 -> LEFT2. 무조건 큰 쪽 -> RIGHT LEFT에 있는 모든 애들은 RIGHT 보다 반드시 작아야 한다. 그래서 LEFT를 최대힙으로 설정. RIGH..
연습 2024. 8. 23. 21:37
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/04   »
일 월 화 수 목 금 토
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30
글 보관함