[백준] 1655 가운데를 말해요

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

숫자가 순서대로 입력되었을때, 숫자들이 계속해서 정렬을 유지해야합니다.

초기에 하나의 큐를 이용하여 값을 정렬하고, 새로운 값이 들어올때 새로운 큐를 만들어 순서를 정렬하였으나 입력의 개수가 많아지게 되어 시간 초과가 발생하였습니다.

 

이후 최소힙과 최대힙을 이용하여 중간값을 유지시키도록 하였습니다.

중간값이 있을때, 중간 값보다 큰 값이 들어오는 경우, 최소힙에 새로운 값을 넣었습니다.

이렇게 하면 중간 값보다 크지만, 그 이후 값들은 작은 값들을 우선적으로 꺼낼 수 있습니다.

중간 값 보다 작은 값은 최대힙에 넣어, 중간 값과 가까운 수를 먼저 꺼낼 수 있도록 하였습니다. 

 

숫자가 짝수개의 길이라면 두개의 값 중 작은 값을 꺼내야 하기에, 중간값보다 작은 값을 저장하는 최대힙으로 숫자 저장을 우선시하였습니다.

중간값 유지를 위해 최소힙과 최대힙의 길이는 항상 같거나, 최대힙이 한개 더 많은 경우가 존재하도록 하였습니다.

2) 알고리즘

• 최소힙
• 우선순위 큐

3) 풀이 코드

사용 언어 - Python

import sys
import heapq as h
sys.stdin = open('input.txt')

N = int(sys.stdin.readline())
min_h = []                              # 최소힙
max_h = []                              # 최대힙

for _ in range(N):
    num = int(sys.stdin.readline())     # 들어갈 숫자

    if len(min_h) == len(max_h):        # 두개의 힙이 길이가 같다면, 우선 최소힙에 추가
        h.heappush(min_h, num)
    elif num > -max_h[0]:               # 새로 들어오는 숫자가 현재 중간값 보다 크면
        h.heappush(min_h, num)          # 최소힙에 추가
    else:                               # 새로 들어오는 숫자가 현재 중간값 보다 작거나 같으면
        h.heappush(max_h, -num)         # 최대힙에 추가
    
    if len(max_h) < len(min_h):         # 최소힙의 길이가 더 길면
        n = h.heappop(min_h)            # 최소힙의 제일 작은 값을 최대힙으로 이동
        h.heappush(max_h, -n)
    elif len(max_h) > len(min_h) + 1:   # 최대힙의 길이가 최소힙보다 2 이상 길면
        n = h.heappop(max_h)            # 최대힙의 최대값을 최소힙으로 이동
        h.heappush(min_h, -n)
    
    print(-max_h[0])                    # 최대힙의 최댓값(중간값)을 출력

---

🔗 문제 링크

- https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다