백준 / 가운데를 말해요 / 1655번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 가운데를 말해요 / 1655번 (골드 2단계)

문제 사이트: https://www.acmicpc.net/problem/1655

 

문제 설명

---

나의 풀이

N = int(input())

result = []
answer = []

for _ in range(N):
    number = int(input())
    result.append(number)
    result.sort()
    r = len(result)

    # result 길이가 2보다 작을 때 (짝수)
    if r < 2 and r % 2 == 0:
        answer.append(min(result))
    # result 길이가 2보다 클 때 (짝수)
    elif r % 2 == 0:
        answer.append(min((result[(r // 2) - 1]), result[r // 2]))
    # result 길이가 1일 때 (홀수)
    elif r == 1:
        answer.append(result[0])
    # result 길이가 3보다 크거나 같을 때 (홀수)
    else:
        answer.append(result[r // 2])

for i in answer:
    print(i)

테스트는 통과했지만 시간초과가 발생한 문제다

import heapq
import sys

input = sys.stdin.readline

N = int(input())
left_heap = []  # 최대 힙 (부호를 반전시켜 구현)
right_heap = []  # 최소 힙
result = []

for _ in range(N):
    number = int(input())

    if len(left_heap) == len(right_heap):
        heapq.heappush(left_heap, -number)
    else:
        heapq.heappush(right_heap, number)

    if right_heap and -left_heap[0] > right_heap[0]:
        left_val = -heapq.heappop(left_heap)
        right_val = heapq.heappop(right_heap)
        heapq.heappush(left_heap, -right_val)
        heapq.heappush(right_heap, left_val)

    result.append(-left_heap[0])

for value in result:
    print(value)

힙을 사용하여 두 자료를 비교하여 문제를 해결했다.

---

※ 알아야 할 것

골드 이상의 문제에서부터는 자료구조를 이해하지 않고 문제에 접근하게 되면 시간 초과가 발생하는 것 같다.

자료구조에 대해 기본적인 이해가 필요하다.