[BOJ] 1655번 가운데를 말해요 / 사용언어 : 파이썬(python)

※ 문제링크

1655번: 가운데를 말해요

해당문제는 우선순위 큐 자료구조를 활용하여 풀어야하는 문제였다. 파이썬에서는 해당 자료구조를 구현할 수 있는 heapq패키지를지원해주고 있어서 활용하여 문제를 해결하였다. 이번 문제를 풀기 위해서는 최대힙과 최소힙 2가지를 응용해야만 했다. heapq패키지는 기본적으로 최소힙만 지원을 해주고 있었기에 최대힙을 사용하기 위해서는 약간의 변형이 필요했다. 자세한 풀이방법과 코드는 아래와 같다.

1. 최대힙과 최소힙으로 사용할 리스트를 생성해준다.

2. 값을 입력받았을 때 총 원소의 갯수가 홀수면 최대힙에, 짝수면 최소힙에 입력받은 값을 넣어준다. 

3. 총 원소의 갯수가 2개 이상일때부터는 최대힙과 최소힙의 첫번째 원소끼리 비교를 하여 최소힙의 변수가 최대힙의 변수보다 작으면 pop명령을 이용하여 해당 원소들의 위치를 바꾸어준다.

4. 입력과 위치변경이 끝난 후에는 최대힙의 첫번째 원소를 출력하여 준다.

(원소의 갯수와 상관없이 문제의 조건상 무조건 최대힙의 첫번째 원소를 꺼내면 조건에 부합합니다.)

5. 입력받은 반복횟수까지 해당 내용을 반복해준다.

+ 시간단축을 위해 sys함수를 사용하였습니다. sys함수 사용시에는 개행문자에 유의하여 사용하시기 바랍니다.

 

import heapq
import sys

def check(max, min): # 힙끼리 값을 비교하고 조건에 충족시 값을 바꿔줄 함수
    if max[0][1] > min[0]:
        heapq.heappush(min, heapq.heappop(max)[1])
        x = heapq.heappop(min)
        heapq.heappush(max, [-x, x])
        return
    else:
        return

max = [] # 최대 힙
min = [] # 최소 힙
N = int(input())
for i in range(1, N+1):
    order = int(input())
    if i < 2:
        if i % 2 != 0:
            heapq.heappush(max, [-order, order])
        else:
            heapq.heappush(min, order)
    else:
        if i % 2 != 0:
            heapq.heappush(max, [-order, order])
            check(max, min)
        else:
            heapq.heappush(min, order)
            check(max, min)
    if i == N:
        sys.stdout.write(f'{max[0][1]}')
    else:
        sys.stdout.write(f'{max[0][1]}\n')

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.