백준 2109 순회강연

https://www.acmicpc.net/problem/2109
정렬을 이용하면 되지만 우선순위 큐를 사용했다.
처음에는 지정된 날짜에만 강연할 수 있다고 생각했으나, 그 이전에도 강연할 수 있었다.

#틀린 코드
import sys
from heapq import heappush
from collections import defaultdict
input = sys.stdin.readline
n = int(input())
heap = defaultdict(list)
day = 0
for i in range(n):
    p, d = map(int, input().split())
    heappush(heap[d], -p)
    day = max(d, day)
ans = 0
for i in range(1, day+1):
    if heap[i]: ans -= heap[i][0]
print(ans)

p를 기준으로 최대 우선순위큐를 만들고 비어있는 날짜에 계속해서 채워주었다.
만약 d 날짜에 강연이 비어있을 경우 p로 채워준다.
그렇지 않을 경우, 1일까지 순차탐색을 해가며 비어있는 날을 p로 채워준다.

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
n = int(input())
heap = []
day = 0
for i in range(n):
    p, d = map(int, input().split())
    heappush(heap, (-p, d))
    day = max(d, day)

pay = [0] * (day+1)
while heap:
    p, d = heappop(heap)
    if pay[d] == 0:
        pay[d] = -p
    else:
        i = d
        while i > 0:
            if pay[i] == 0:
                pay[i] = -p
                break
            i -= 1
print(sum(pay))

다만 순차탐색이기 때문에 해당 풀이는 매우 느리다.

그래서 다른 사람 풀이를 참고했다.

days = list(range(0, 10001))
def find_empty(i):
    if days[i] == i:
        return i
    days[i] = find_empty(days[i])
    return days[i]

특정 날짜를 채우면 days의 채워진 날짜요소가 왼쪽 인덱스를 가리키고, 이것이 인덱스와 요소가 일치할 때까지 재귀를 반복하고 일치한 요소 발견 시 해당 인덱스를 반환한다. 따라서 내용물이 차있는 인덱스는 모두 왼쪽의 비어있는 인덱스를 가리키거나, 갱신된다. days에는 해당 날짜를 저장한다.

또한 if문에는 추가적으로 i ≠ 0이라는 조건이 붙는다. 계속해서 왼쪽을 가리키기 때문에 이러한 조건을 걸어둔 것이다.

이 메소드를 통해 탐색 시간이 크게 줄었다.

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
days = list(range(0, 10001))
def find_empty(i):
    if days[i] == i:
        return i
    days[i] = find_empty(days[i])
    return days[i]

n = int(input())
heap = []
day = 0
for i in range(n):
    p, d = map(int, input().split())
    heappush(heap, (-p, d))
    day = max(d, day)

pay = [0] * (day+1)
while heap:
    p, d = heappop(heap)
    i = find_empty(d)
    if i != 0 and pay[i] == 0:
        pay[i] = -p
        days[i] -= 1
print(sum(pay))