(백준 알고리즘 문제풀이) 1655번 가운데를 말해요

문제

 

문제 링크

 

문제 접근

• 우선순위를 가진 Queue인 우선순위 큐를 이용하면 될 것이다.
• N개 만큼은 정수형을 받았을 때, 순위에서 가운데 숫자를 말하면 되는 것이다.
• 만약 N개중에 짝수번째라면 우선순위 큐 1에 푸쉬를 해준다. 하지만 홀수번째라면 또 다른 우선순위 큐 2에 받아온 값에 -1을 곱한 값을 푸쉬해준다.
• 우선순위 큐 1의 가장 큰 값의 절대값이 우선순위 큐 2의 가장 작은 값보다 작게된다면 중간수가 변하는 것이므로 두개의 부호를 바꾸어주어 서로 스왑해준다.
• 출력: t에서 가장 작은 값을 부호를 바꾸어 출력하면된다.

코드

import sys, heapq

# 1~2: 1, 3~4: 2, 5~6: 3 ......
N = int(sys.stdin.readline())
q = list()
t = list()
for i in range(N):
    temp = int(sys.stdin.readline())
    if i % 2 == 1:
        heapq.heappush(q, temp)
    else:
        heapq.heappush(t, -temp)

    if q and -t[0] > q[0]:
        heapq.heappush(q, -heapq.heappop(t))
        heapq.heappush(t, -heapq.heappop(q))

    print(-t[0])

느낀점

Queue를 모른다면 문제에 대한 접근을 엄청 어렵게 했을 것 같다. 확실히 코딩이든 어떤 공부를 하든 아는것이 힘이된다. 더욱 공부하며 성장할 수 있는 내가 되어야겠다.