×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,045,673명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

문제 출처 :


https://www.acmicpc.net/problem/1655



알고리즘 분석 :


문제 해결에 필요한 사항

1. 최대 힙, 최소 힙

2. Priority Queue

3. pq로 중간 값 구하는 방식


중간값 구하기 알고리즘은 다음과 같다.


1. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다.

2. 최대 힙의 최대 원소는 최소 합의 최소 원소보다 작거나 같다.

이때 알고리즘에 맞지 않다면 최대 힙, 최소 힙의 가장 위의 값을 swap해준다.

[결과] 이때 이 두가지 규칙을 유지해 준다면 항상 최대 힙 top값이 중간값이 된다.


예시 그림을 통해 어떻게 구현을 하는지 알아보자.


1,2,3,4,5를 순서대로 넣을 때 중간값이 어떻게 구성되나 확인해본다.



처음에는 무조건 최대 힙에 값을 넣어준다. 왜냐면 최소 힙에 넣는 순간 (1)번 규칙에 어긋나게 된다.

이때 중간 값은 값 자체가 1개 뿐이니 1이다.



2를 넣을 때는 최대 힙에 넣는 순간 (1)규칙에 어긋나게 되므로 최소 힙에 넣는다.

그리고 (2)번 규칙에서 최대 힙의 최댓값이 최소 힙의 최솟값 보다 작거나 같으므로 swap하지 않는다.

이때 중간값은 1이다. 

(문제 내에 설명 :: 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.)




(1)번 규칙에 의해 3은 최대 힙에 들어갔지만, (2)번 규칙에 현재 어긋난다.

따라서 3과 2를 swap해준다.




swap된 결과로 중간값이 1->3(아주잠깐)->2로 변하였다.



(1)번 규칙에 의해 최소 힙에 4를 넣어준다.



5를 넣을 때는 (1)번 규칙에 의해 5를 최대 힙에 넣어준다.


이때 최대 힙의 top 값은 5, 최소 힙의 top 값은 3이므로 (2) 규칙에 위배된다. 따라서 swap



결과적으로 1,1,2,2,3이라는 중간값이 생기게 된다.


1 :: 1

1, 2 :: 1

1, 2, 3 :: 2

1, 2, 3, 4 :: 2

1, 2, 3, 4, 5 :: 3


소스 코드 : 


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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <functional>
 
#define MAX_N 100002
 
using namespace std;
 
priority_queue<int, vector<int>, less<int>> max_heap;
priority_queue<int, vector<int>, greater<int>> min_heap;
int arr[MAX_N];
 
/*
중간 값 구하기 알고리즘
1. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다.
2. 최대 힙의 최대 원소는 최소 합의 최소 원소보다 작거나 같다.
이때 알고리즘에 맞지 않다면 최대 힙, 최소 힙의 가장 위의 값을 swap해준다.
*/
 
int main()
{
    int n, val;
    scanf("%d"&n);
 
    while (n--)
    {
        scanf("%d"&val);
 
        // By 1
        if (max_heap.empty())
            max_heap.push(val);
 
        else if (max_heap.size() == min_heap.size())
            max_heap.push(val);
 
        else
            min_heap.push(val);
 
        // By 2
        if (!max_heap.empty() && !min_heap.empty() && !(max_heap.top() <= min_heap.top()))
        {
            int a = max_heap.top();
            int b = min_heap.top();
 
            max_heap.pop();
            min_heap.pop();
 
            max_heap.push(b);
            min_heap.push(a);
        }
 
 
        printf("%d\n", max_heap.top());
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[1697번] 숨바꼭질  (0) 2017.02.28
[2014번] 소수의 곱  (1) 2017.02.28
[1655번] 가운데를 말해요  (0) 2017.02.28
[11286번] 절대값 힙  (0) 2017.02.28
[1715번] 카드 정렬하기  (0) 2017.02.28
[2583번] 영역 구하기  (0) 2017.02.27