백준 1655 가운데를 말해요 파이썬

백준 1655 가운데를 말해요 풀이

접근방식

1. heapq 자료구조를 이용합니다.
2. 중앙값을 출력할 leftH과 그보다 큰 값들을 저장할 rightH를 활용합니다.
3. leftH는 최대힙을, rightH는 최소힙을 사용합니다.
4. 최대힙을 사용하기 위해서 heap에 -를 붙여서 넣어줍니다.
5. 그렇게 되면 leftH에는 자연스럽게 부모노드가 자식노드보다 작은 값을 저장하게 됩니다.
6. 이때, if문을 통해서 만약 rightH에 들어가야 할 차례이지만, 중간값보다 작은 값이
   들어가게 된다면 leftH와 rightH에서 각각 heappop을 해서 서로의 원소를 바꿔줌으로써 균형을 맞춰줍니다.

이번 문제는 우선순위큐, 최대/최소 힙큐를 사용해야 하는 문제입니다.
기존에 이 개념에 대해서 잘 몰라서 여러 자료를 찾아보면서 정답코드를 공부할 수 있었습니다.

우선, 그 전에 단순히 리스트의 인덱싱을 활용하여 풀었던 오답코드는 아래와 같습니다.

# 오답코드
import sys

input = lambda: sys.stdin.readline().rstrip()

n = int(input())
arr = []
for _ in range(n):
    arr.append(int(input()))
    arr.sort()
    if len(arr) % 2 == 0:
        print(arr[len(arr)//2-1])
    else:
        print(arr[len(arr)//2])

정답코드

import sys
import heapq
input = lambda: sys.stdin.readline().rstrip()
n = int(input())

leftH = []
rightH = []
answer = []
for i in range(n):
    num = int(input())
    if len(leftH) == len(rightH):
        heapq.heappush(leftH, -num)
        # print("leftH", leftH)
        # print("rightH", rightH)
    else:
        heapq.heappush(rightH, num)
        # print("leftH", leftH)
        # print("rightH", rightH)
    
    
    if rightH and rightH[0] < -leftH[0]:
        leftValue = heapq.heappop(leftH)
        rightValue = heapq.heappop(rightH)

        heapq.heappush(leftH, -rightValue)
        heapq.heappush(rightH, -leftValue)
        # print("changed left", leftH)
        # print("changed right", rightH)
    print(-leftH[0])

참고자료

https://art-coding3.tistory.com/44
https://hongcoding.tistory.com/93
https://youtu.be/AjFlp951nz0

위의 블로그와 나동빈님의 유튜브 자료 등을 활용하여 힙큐에 대해서 배울 수 있었고,

모듈 사용법과 처리 속도를 바탕으로 앞으로 더 다양한 알고리즘 문제에 활용하면 좋을 것 같습니다.

저 같은 경우, 각각의 힙큐가 어떤 식으로 변화되는지 확인하기 위해서

힙큐에 원소가 저장될 때와 원소가 바뀔 때를 출력하도록 해서 이해하는데 도움을 얻었습니다.

직관적으로 와닿지 않으신 분들도 이 방법을 활용하시면 좋을 것 같습니다.

해당 문제는 골드 2레벨의 문제로,

우선순위큐와 완전 이진 트리에 대한 개념을 알고 있어야 풀 수 있는 문제입니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady