알고리즘/백준(BOJ)
[백준/C++] 1655번 가운데를 말해요
https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 매번 입력마다 정렬해서 가운데 값을 출력하면 시간초과가 난다ㅜㅜ 0.1초안에 해결해야하는데, 최대 입력이 100,000이므로 O(N^2)으로는 해결할 수 없다는 뜻이다. 이 문제는 2개의 우선순위 큐를 활용하면 되는데, 활용조건은 다음과 같다. 1. 최소 힙의 값들은 모두 최대 힙보다 커야한다. 2. 최대 힙의 크기가 최소 힙의 크기보다 1보다 크거나 같도록 유지한다. 3. 최..
