반응형

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

+ Recent posts