백준 1655 가운데를 말해요

우선순위 큐 사용 방법

최소 힙

최소힙 생성

		import heapq
		
		que=[40,50,10,15,30,100,40]
		
		heapq.heapify(que)     # 이미 존재하는 리스트를 즉각적으로 heap으로 변환함 
		
		print(que)
        
        >>>[10, 15, 40, 50, 30, 100, 40] 
        
        

pop 하면 작은 값부터 pop된다 (작은 값이 우선순위)

		for _ in range(len(que)):
		    print(heapq.heappop(que),end=' ') 
            
            >>>>10 15 30 40 40 50 100
		

최대 힙

	파이썬의 heapq 모듈은 최소 힙으로 구현되어 있기 때문에 최대 힙 구현은 다음과 같이 한다. 
	
		
		import heapq
		
		que=[40,50,10,15,30,100,40]
		negative_que=[]
		
		for i in que:
		    negative_que.append(-i)    #음수로 데이터를 변환한다.
		    
		heapq.heapify(negative_que)
		for _ in range(len(negative_que)):
        print(-heapq.heappop(negative_que),end=' ')  #다시 양수로 바꿔서 데이터를 출력한다. 
        
        >>>>100 50 40 40 30 15 10  (큰 값이 우선순위로 출력된다.) 

문제 적용

백준 1655번 문제 요약

	입력값을 받을 때마다 쌓인 데이터 중에서 중간값을 출력. 
    ( 만약 데이터의 개수가 짝수 예를들어 1 8 10 20 일 경우 작은 숫자인 8을 출력 )

문제 해결법

	예를 들어 1 8 10 20 의 중간값을 출력한다는 것은 
	
	(1 **8** ) (10 20) 표시한 부분(8)을 출력한다는 것.  
	
	->두 개의 자료구조를 만들어서 왼쪽의 끝에 있는 요소를 출력하면 되겠다. 
	
	왼쪽에는 작은 값들을 오른쪽에는 왼쪽보다 큰 값들을 저장하는 방법
	
		데이터를 두 개의 자료구조로 번갈아서 받고 
		
		받을 때마다 "왼쪽max > 오른쪽min" 이면 둘의 위치를 바꾼다.
		
	위 과정에서 우리가 필요한 것은 두 자료구조의 최댓값 또는 최솟값밖에 없다 
    
    -> 자료구조로 우선순위 큐를 사용한다. 

		

문제 코드

	from sys import stdin
	import heapq
	stdin = open("input.txt","r")
	input=stdin.readline
	n=int(input())
	left=[]
	right=[]
	for _ in range(n):
	    number=int(input())
	    
	    if len(left)==len(right):
	        heapq.heappush(left,-number)
	    else:
	        heapq.heappush(right,number)
	    
	    if right and -left[0]>right[0]:
	        left_val=heapq.heappop(left)
	        right_val=heapq.heappop(right)
	        
	        heapq.heappush(left,-right_val)
	        heapq.heappush(right,-left_val)
	        
     print(-left[0])