우선순위 큐 재활하면서 응용력 키우기1 -카드 정렬하기, N번째 큰 수

1. 문제1

 

1715번: 카드 정렬하기 (acmicpc.net)

1715번: 카드 정렬하기

 

2. 풀이

 

문제를 잘 보면 매 순간 최소인 얘들을 더해나가면 최적이 될 것 같다는 생각이 든다

 

우선순위 큐에 주어진 수를 모두 넣는다

 

큐가 빌때까지 정수를 2개 뽑아, 두 수를 더한 다음에, 다시 우선순위 큐에 넣어준다.

 

그러니까, 10, 20, 40이 있는데, 10,20을 뽑아 10+20을 한 다음에 40을 바로 뽑는게 아니고,

 

30을 우선순위 큐에 넣어서 30,40이 된 상태에서, 다시 30,40을 뽑아 더해준다

 

import heapq
from sys import stdin

n = int(stdin.readline())

q = []

count = n

answer = 0

for _ in range(n):
    
    a = int(stdin.readline())

    heapq.heappush(q,a)

while q:

    x = heapq.heappop(q)

    count -= 1

    if count == 0:

        break

    y = heapq.heappop(q)

    count -= 1

    answer += (x+y)

    if count != 0:

        heapq.heappush(q,(x+y))

        count += 1

print(answer)

 

근데 이제 문제를 잘 보면, 우선순위 큐에 수 하나가 남으면 그것을 더하는건 아니다

 

따라서 정리하자면, 우선순위 큐에 모든 수를 일단 넣고 항상 최솟값만을 뽑아준다.

 

count라는 변수는 우선순위 큐에 들어있는 원소의 수를 관리한다

 

하나 뺀 x에서 count가 0이 되면, 우선순위 큐에 하나만 있다는 뜻으로,

 

카드를 모두 정리했기때문에 더 이상 answer에 더하지 않고 바로 break

 

y까지 빼는데 성공했다면, answer에 x+y를 더해주고, 우선순위 큐의 원소가 남아있다면, x+y를 우선순위 큐에 넣어준다

 

하지만 우선순위 큐에 원소가 없다면 넘어가고 반복문을 빠져나가준다

 

 

3. 문제2

 

2075번: N번째 큰 수 (acmicpc.net)

2075번: N번째 큰 수

 

4. 풀이

 

n*n개의 수를 우선순위 큐에 넣어서 하나씩 뽑아 n번째 나오는 수가 정답이기는 한데

 

메모리 제한이 12mb라서 1500*1500개의 수를 모두 저장하기에는 무리가 있다

 

메모리 제한을 어떻게 피할 수 있을까?

 

1가지 방법은 1줄씩 입력받아 우선순위 큐에 저장하는데, 우선순위 큐에 항상 1등부터 n등까지의 수가 있도록 만드는 것이다

 

그러니까 일단 1줄 입력받아 우선순위 큐에 모두 저장하면, 1등부터 n등까지의 수가 있고

 

다음 줄부터 일단 1줄 입력받고 우선순위 큐에 넣을려고 하는데

 

수를 하나 넣어서 1등부터 n+1등까지 있는 상태에서, n+1등을 빼서 항상 1등부터 n등까지 있도록 해준다.

 

모든 줄을 입력받는다면, n*n개의 수중에서 1등부터 n등까지만 남아있을 것이다.

 

따라서 우선순위 큐에서 수 하나만 빼면 그 수가 n번째로 큰 수가 된다.

 

import heapq
from sys import stdin

n = int(stdin.readline())

min_heap = []

q = list(map(int,stdin.readline().split()))

for i in q:
    
    heapq.heappush(min_heap,i)

for _ in range(n-1):
    
    q = list(map(int,stdin.readline().split()))

    for i in q:
        
        heapq.heappush(min_heap,i)
        heapq.heappop(min_heap)
    
print(heapq.heappop(min_heap))

 

여기서 수를 빼서 1~n-1등인 상태에서 수를 넣어 1~n등인 상태로 만드냐..

 

수를 넣어서 1~n+1등인 상태에서 수를 빼서 1~n등인 상태로 만드느냐 차이가 있는데

 

전자는 오답이다

 

import heapq
from sys import stdin

n = int(stdin.readline())

min_heap = []

q = list(map(int,stdin.readline().split()))

for i in q:
    
    heapq.heappush(min_heap,i)

for _ in range(n-1):
    
    q = list(map(int,stdin.readline().split()))

    for i in q:
        
        heapq.heappop(min_heap)
        heapq.heappush(min_heap,i)
    
print(heapq.heappop(min_heap))

 

input
2
3 1
4 2

 

집어넣으면 정답이 3인데 2가 나옴