1655. 가운데를 말해요 (우선순위 큐)

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

 

---

풀이

 

import sys, heapq

input = sys.stdin.readline

n = int(input())

left_h =[]
right_h = []

for i in range(n):
    num = int(input())
    
    if len(left_h) == len(right_h): #원소의 개수가 짝수일 때
        heapq.heappush(left_h, -num) #left의 원소들이 더 작을 수밖에 없으니 내보내는 걸로.
    else:
        heapq.heappush(right_h, num)
    
    #작은 수들의 [0]=최소값(실제는 최대값)이 큰 수들의 최소값[0]보다 크면
    if right_h and -left_h[0] > right_h[0]: 
        #자리를 바꿔준다.
        #1. 각 배열의 최소, 최대를 나타내는 것들을 pop하여 해당 변수들에 할당
        rights_min = heapq.heappop(right_h)
        lefts_max = -heapq.heappop(left_h) #!(1)반대로 넣을 때는 항상 부호에 신경쓰자
        #2. 있어야할 자리에 넣어준다(자리교체)
        heapq.heappush(left_h, -rights_min) #! (2)
        heapq.heappush(right_h, lefts_max) #! (1)에서 말고 여기서 부호를 붙여도 된다.
    
    #for문이 돌 때마다 중간값 출력. 출력 시에는 원본으로 복원하기
    print(-left_h[0])

 

설명

 

가운데값을 찾아내야 하므로 반을 잘라 왼쪽, 오른쪽으로 작은 수들, 큰 수들로 크게 구분하여 풀어나가는 문제입니다.

 

여기서 핵심은 처음에 원소를 왼쪽부터 넣는다는 것입니다. 처음도 왼쪽 오른쪽의 개수가 0개로 동일하니까요!

짝수개수일 때 왼쪽부터

홀수개수일때는 오른쪽에 넣기 시작

 

왼쪽에 넣을 때는 부호에 -로 변환하고, 반대로 넣을 때마다 항상 이 왼쪽에 들어갈 요소들의 부호를 신경써야 합니다.

1. 왼쪽에 값을 넣을 때

2. 대소비교할 때

3. 왼쪽 변수를 뜻하는 값에 할당할 때 (or 4번에서 처리가능)

4. 자리를 바꿔서 왼쪽에 값을 넣을 때

5. 최종적으로 왼쪽의 [0]을 출력할 때

 

 

• 최대 힙 (left_heap): 현재까지의 숫자 중 작은 절반을 저장하고, 이 힙의 루트는 중간값에 해당하거나, 중간값보다 작아야 하는 값입니다.
• 최소 힙 (right_heap): 현재까지의 숫자 중 큰 절반을 저장하고, 이 힙의 루트는 항상 최대 힙의 루트보다 큽니다.

 

 

가운데 값을 말하려면 두 개를 쪼개어 각 배열의 요소를 비교해야하는데, 문제는 서로 양쪽끝에서 다가온다는 것입니다.

이럴 경우 한 쪽은 한 배열에서 최소값을, 한 쪽은 배열에서 최대값을 내어놓고 비교를 해야합니다.

요소는 추가하며 비교해야 하기에 [n]를 읽는 것보다 [0]를 읽는 게 효율적이고,

무엇보다 우선순위큐에서는 최소힙의 규칙을 따르기 때문에 [0]를 기준으로 출력하는 게 맞습니다.

 

또한 파이썬에서는 최소힙만 제공하기에 숫자가 작은 쪽들을 왼쪽에 위치시켰을 때, 마이너스 부호를 붙여 최대힙처럼 사용해줘야 중간값과 가까운 요소를 비교할 수 있습니다.

 

Q. 왼쪽의 작은 수들과 오른쪽의 큰 수들에 저장되는 원소들을 보니, 오름차순으로 정렬eh 되어있지 않고, 왼쪽에 있는 수가 오른쪽보다 더 커서 혼란스러워요. 이거 그냥 냅둬도 되나요?

 

왼쪽 오른쪽에 추가되는 배열들을 보면서, 오름차순으로 정렬되어있지 않아 혼동을 일으키지 않아도 됩니다.

우선순위큐 문제에서 핵심은 최소힙의 자리, 즉 부모노드인 [0]자리의 값만 따지기 때문에 비교되지 않는 대상에는 신경쓰지 않아도 됩니다.

 

+)

왜 right_h and?

 

if문에서 해당 리스트가 존재하는지 True, False로 확인할 때 "리스트명 and"로 사용할 수 있는데요

(존재 시 기본판정은 True 입니다.)

 

첫 번째 입력이 있을 때 숫자는 left_h에 추가되고, 그 이후로는 left_h에 항상 값이 있게 됩니다. 하지만 right_h는 아닙니다.

pop으로 힙큐에서 원소를 꺼내야하는 경우는 일단 left_h에 원소는 이미 존재하고, right_h와 비교가 배열위치에 변동을 일으킬 때인데요, 이 경우 right_h 에서 heappop으로 값을 꺼내어 바꿔줘야할 때 비어있으면 에러를 냅니다. right_h 가 비어있진 않은지 확인해야 하는 것입니다.

 

아래는 1개씩 넣을 때 어떻게 리스트가 변하는지 과정의 일부를 보여주고 있습니다.

high = right_h, low = left_h 라고 생각하며 봐주세요.

 

마지막 5를 넣을 때는 low에 [-5, -2, -1, 99] / high = [5, 10, 75] 로 들어가며 median으로 5가 출력됩니다.

 

실제로 여기서 값을 pop하여 좌우로 이동하진 않았지만 다른 예시에서는 쓰입니다.

그리고 넣다보면 똑같은 5를 삽입하게 되는데요, 같은 값이 존재할 때 다르게 처리해야하나? 싶지만

그냥 현재 들어가있는 개수가 짝수인지 홀수인지만 따져서 왼쪽, 오른쪽으로 넣어주면 됩니다.

---

 

😎또 다시 보는 기초!

*참고로 여기서 strip을 쓰지 않아도 동작합니다.

 

• 장점: 입력을 하나씩 처리하므로 메모리를 효율적으로 사용할 수 있고, 즉시 중간값을 계산할 수 있습니다.
• 단점: 반복문 안에서 매번 입력을 받고 처리해야 하기 때문에 코드가 조금 더 길어질 수 있습니다.
• range(n)을 사용하는 것이 맞습니다. 각 입력에 대해 하나씩 처리하기 때문에, range(n)으로 루프를 돌면서 입력을 받습니다.

 

 

• 장점: 코드가 깔끔하고, 입력을 한 번에 받을 수 있습니다.
• 단점: 메모리 사용이 증가할 수 있고, 입력을 받은 후에 중간값을 처리하기 때문에 즉시성을 잃을 수 있습니다. 이 방식은 전체 데이터를 한 번에 처리하는 경우에 더 적합합니다.
• 이 방법에서는 range(n)을 사용하여 입력을 받을 수 있습니다.

 

어떤 방법이 더 적합한가?

1655 문제에서는 첫 번째 방법이 더 적합합니다. 이유는:

• 각 숫자가 입력될 때마다 중간값을 출력해야 하기 때문에, 입력을 받으면서 바로 처리하는 것이 중요합니다.
• 입력을 모두 받은 후에 처리하는 방식(두 번째 방법)은 중간값을 실시간으로 출력해야 하는 문제의 특성상 적합하지 않습니다.

따라서, for문을 사용하여 range(n)으로 입력을 하나씩 받아 처리하는 첫 번째 방법이 적합합니다.

 

---