우선순위큐2 [백준 2696번] 중간값 구하기 난이도: 골드 II 문제 링크: https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 입력받은 n개의 정수 (n은 홀수) 중, 차례로 읽으며 홀수번째 수를 읽을 때마다 그 수까지의 중간값을 출력하는 문제입니다. 가장 먼저 떠오른 생각은... 매 홀수번째 수를 읽을 때마다, 지금까지 읽은 수를 정렬한 후 중간값을 읽자... 인데 그러면 원소의 개수가 n개라면 총 (n/2)번 정렬을 해야 합니다. Quick sort가 평균 .. 2021. 8. 29. [백준 1655번] 가운데를 말해요 난이도: 골드 2 문제 링크: www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 제한 시간이 매우 짧은 (0.1초) 문제입니다. 반면 메모리는 상대적으로 넉넉한 편인 문제 같네요. 저는 다음과 같이 접근했습니다. 두 개의 Priority Queue minPQ, maxPQ를 둡니다. minPQ는 제일 작은 수가 top에, maxPQ는 제일 큰 수가 top에 위치합니다. 수를 입력 받아서 다음을 기준으로 push합니다. maxPQ의 element .. 2020. 12. 23. 이전 1 다음
