📚 2109 - 순회강연

순회강연

이해

d : 일(day)
p : 강연료

하루에 최대 한 곳에서만 강연할 수 있다.
최대 한 곳에서만 강연을 할 수 있다.

이와 같은 문제는 우선순위 큐와 그리디 알고리즘을 이용한다면 풀 수 있는 문제이다.

딕셔너리를 이용하여, key는 일, value : 강연료를 저장한다.
정렬을 할 때는 day를 기준으로 오름차순 정렬후, 강연료를 내림차순으로 정렬한다.

검토를 할 때는 입력된 d값 중 가장 큰 값 (마지막 일)을 기준으로 반복문을 돌린다.
돌릴 때, 현재 n일날 사용할 수 있는 강연료를 찾는다.

• 만약, n일날 사용할 수 있는 강연료가 우선순위 큐 첫 번째 값보다 크거나
• 우선순위 큐 저장소 길이가 i보다 작다면, heappush()를 한다.
  • 만약 우선순위 큐 저장소가 n(일)와 같다면 이전에 저장되어있는 데이터를 꺼내고 새로운 값을 heappush 한다.

소스

내가 푼 소스

import sys  
import heapq  
  
read = sys.stdin.readline  
  
n = int(read())  
  
dist = {i: [] for i in range(10001)}  
  
max_day = 0  
  
for i in range(n):  
    p, d = map(int, read().split())  
    dist[d].append(p)  
  
    if max_day < d:  
        max_day = d  
  
dist = list(dist.items())  
dist.sort(key=lambda x: (x[0], x[1].sort(reverse=True)))  
dist = dict(dist)  
queue = [0]  
  
for i in range(1, max_day + 1):  
    cur_day = min(i, len(dist[i]))  
  
    for j in range(cur_day):  
        if dist[i][j] > queue[0] or len(queue) < i:  
            if len(queue) == i:  
                heapq.heappop(queue)  
            heapq.heappush(queue, dist[i][j])  
print(sum(queue))

잘 구현한 답안

import heapq  
import sys  
  
read = sys.stdin.readline  
  
n = int(read().strip("\n"))  
  
lectures = []  
  
for _ in range(n):  
    p, d = map(int, read().split())  
    lectures.append([p, d])  
  
lectures.sort(key = lambda x: x[1])  
  
queue = []  
  
for pay, day in lectures:  
    heapq.heappush(queue, pay)  
  
    if day < len(queue):  
        heapq.heappop(queue)  
  
print(sum(queue))

• 모범 답안이다.
• 일차원 for문 밖에 없다.
• 시간복잡도가 단축되었다.