개구리의 개발 블로그 개구리의 개발 블로그

백준 1655번 가운데를 말해요 파이썬 문제 링크 - https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net N=10만이고 시간 제한이 0.1초인 문제다. 가운데 값이 갱신되는 블랙 박스가 있다고 할 때, 삽입과 조회가 모두 O(log N)안에 해결되어야 한다. B+tree가 생각났는데 이 때부터 계속 트리 구조를 수정하면서 그림을 그렸다. 제대로 구현되는 게 없어서 힌트를 보고 풀었다. 우선순위 큐를 사용하여 가운데에서 가장 가까운 ..