힙 썸네일형 리스트형 백준 1655번 가운데를 말해요 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 N개의 정수를 입력받아 1번째, 2번째, ... N번째 정수까지만 보았을 때 각각의 중앙값들을 출력하는 문제입니다. 풀이 단순히 배열을 사용하여 입력받을 때마다 배열을 정렬한다면 O(N^2)이므로 시간초과일 것입니다. 힙을 이용하여 O(NlogN)으로 해결할 수 있습니다. 지금까지 입력받은 수 중 절반의 작은 수들은 최대 힙에, 나머지 절반의 큰 수들은 최소 힙에 저장합니다... 더보기 이전 1 다음
