반응형
https://www.acmicpc.net/problem/2696
2696번: 중앙값 구하기
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주
www.acmicpc.net
해결 방법 : 배열 기반 우선순위 큐
- input sequence를 순차적으로 배열에 넣되, 정렬된 상태로 넣으면된다.
- 정렬 상태를 유지하면서 insert하기 위해 이진 탐색을 사용하여 탐색을 O(logN)으로 한다.
import sys
input = sys.stdin.readline
import bisect
def solution(l, seq):
answer = []
PQ = [] # 정렬 배열
for i, s in enumerate(seq):
bisect.insort_left(PQ, s) # 이분 탐색으로 정렬 insert
if (i + 1) % 2 == 1: # 홀수
answer.append(str(PQ[(i + 1)//2])) # 중앙값
return len(answer), ' '.join(answer)
if __name__ == '__main__':
T = int(input())
for _ in range(T):
l = int(input())
seq = []
for _ in range((l//10) + 1):
seq.extend(list(map(int, input().split())))
num, result = solution(l, seq)
print(f'{num}\n{result}')
반응형
'IT study > 알고리즘 문제 풀이' 카테고리의 다른 글
백준 1071 : 소트 (0) | 2021.07.23 |
---|---|
백준 9489 : 사촌 (0) | 2021.07.22 |
프로그래머스 - 중력 작용 (0) | 2021.07.17 |
프로그래머스 : N으로 표현 (0) | 2021.06.30 |
프로그래머스 : 순위 (0) | 2021.06.29 |