[C/C++] 백준 #1655 가운데를 말해요(힙)
이번 문제는 구간의 중간수 구하던 문제와 같이 두개의 힙을 이용해서 풀 수 있는 문제입니다. 왼쪽은 최대힙(max heap)을 오른쪽은 최소힙(min heap)을 운영합니다. 왼쪽 힙은 오른쪽 힙의 개수보다 1개 크거나 같아야 합니다. 1, 5, 2, 10, -99, 7, 5 순으로 숫자가 불리었고, 이번에 10이 불리는 차례였다면, 왼쪽의 최대힙은 [ 2, 1 ] 이 들어가 있고, 오른쪽 최소힙은 [5]가 들어가 있습니다. 10을 왼쪽힙의 최대값 2와 비교해서 작으면 왼쪽에, 크면 오른쪽에 넣습니다. 이 경우엔 2보다 큰 수이므로 오른쪽에 들어가 있게 됩니다. 그러면 [ 2, 1 ]과 [ 5, 10 ] 이 되고, 두 힙의 크기가 같으니, 힙간 원소 이동은 없습니다. 왼쪽힙의 가장 큰 값을 출력하면 2가..
2022. 9. 22.
