완전 탐색
입력될 때마다 입력된 수를 탐색해서 중간값 구하기
시간복잡도 : 1+2+...+N = N(N-1)/2 = O(N^2)
-> N이 100,000일 경우 시간초과
중간값 : 중간값을 기준으로 중간값보다 작은 수의 집합 A, 큰 수의 집합B
- ⭐️ 유지해야 하는 상태 :
중간값보다 작은 수의 개수 n(A)
중간값보다 큰 수의 개수 n(B) 가 유지 되어야 함. (또는 한 개 차이)- 그 다음 입력되는 값이
중간값보다 작으면 -> 중간값보다 작은 수의 집합
중간값보다 크면 -> 중간값보다 큰 수의 집합
유지해야 하는 상태로 조정
💡 TIP
N = 100,000 -> O(NlogN)
