Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- boot sequence
- ps
- BST
- 백준
- leetcode
- Network
- swea
- 릿코드
- baekjoon
- 데이터베이스
- Embedded
- Djikstra
- 프로그래머스
- 관계형 모델
- Database
- 문제풀이
- DB
- BHS
- 전송 계층
- Application Layer
- 임베디드
- STL
- 다익스트라
- 자료구조
- dp
- 부트시퀀스
- 응용 계층
- Transport layer
- 네트워크
- C++
Archives
- Today
- Total
BOBO's Note
[ LeetCode ] 480. Sliding Window Median 본문
https://leetcode.com/problems/sliding-window-median/
풀이 방법
슬라이딩 윈도우에 속한 값들 중 중간값을 찾는 문제이다. 중간값은 정렬했을 때, 가장 가운데에 있는 값이다. 중간값를 쉽게 찾을 수 있도록 정렬되고, 중복된 원소를 저장할 수 있는 multiset을 사용하자.
multiset에 슬라이딩 윈도우에 속하는 값들을 모두 넣고, 그 중 가운데에 있는 원소를 찾는다. 이때, 가운데에 있는 원소를 찾는 것은 슬라이딩 윈도우 크기가 K일 때, O(K)의 시간이 걸린다.
auto mid = next(mset.begin(), k/2); // O(k)
따라서 매번 가운데 원소를 찾는 것이 아니라, 처음 한번만 가운데 원소를 가리키는 iterator를 찾고, 그 다음부터는 새로 추가할 원소 및 삭제할 원소들의 값에 따라 iterator를 적절히 업데이트해나간다.
// insert
mset.insert(nums[i]);
if(nums[i] < *mid) mid--;
// erase
if(nums[i-k] <= *mid) mid++;
mset.erase(mset.lower_bound(nums[i-k]));
새로 추가한 원소가 기존의 중간값보다 작다면, 한칸씩 밀리면서 iterator가 중간보다 오른쪽 위치를 가리키게 될테니 iterator를 감소시킨다.
그리고 삭제할 원소가 중간값보다 작거나 같으면 삭제된 후 한칸씩 밀려올테니 미리 iterator를 증가시킨다.
한편, 슬라이딩 윈도우 크기가 짝수이면 가운데 두 원소의 평균값이 중간값이 되는데, 다음과 같이 계산할 수 있다.
double median = *mid;
if(k % 2 == 0){
median += *prev(mid, 1);
median /= 2;
}
전체 코드는 여기서 확인할 수 있다.
'Algorithm > Problem Solving' 카테고리의 다른 글
[ LeetCode ] 98. Validate Binary Search Tree (0) | 2020.06.28 |
---|---|
[ 프로그래머스 ] N으로 표현 (0) | 2020.06.26 |
[ Baekjoon ] 2110. 공유기 설치 (0) | 2020.06.24 |
[ SWEA ] 5644. 무선 충전 (0) | 2020.06.06 |
[ SWEA ] 5658. 보물상자 비밀번호 (0) | 2020.06.06 |
Comments