[백준] 13904번: 과제

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

initial

Ooh finally solved one on my own! So initially i thought it was similar to 공항 question that I did but we cant use union find here cuz we need to find the total reward. So i rolled my brain on and on until I suddenly thought of an approach that used heap’s length and something like if length is shorter we add the reward. So I tried thinking of a pattern to use this and voila!

So we first sort the list based on the days (not reward cuz if we have reward 1 on day 1 and reward 10 on day 69, getting the highest reward on day 69 first means we cant get that reward 1 on day1). Then, we consider the edge case where if len of heap is 0, we just add whatever. The main logic is if current day is larger than the length of heap, we append the reward. BUT else, that means if heap[0] has a lower reward than the current reward, then we are gonna pop that lower reward and push the higher current reward instead.

solution

import heapq
import sys
input =sys.stdin.readline

n = int(input())
lst = [list(map(int, input().split())) for _ in range(n)]
lst.sort(key=lambda x: x[0])
heap = []
heapq.heapify(heap)
ans = 0

for i in range(n):
    day, reward = lst[i]
    if not heap:
        heapq.heappush(heap, reward)
    else:
        if len(heap) < day:
            heapq.heappush(heap, reward)
        else:
            if heap[0] < reward:
                heapq.heappop(heap)
                heapq.heappush(heap, reward)

print(sum(heap))

complexity

log n for heap operations right
n log n for sort
n space?

Let's analyze the time and space complexity of the provided code:

Time Complexity:

1. Sorting: The initial sorting of the lst list has a time complexity of O(n log n), where n is the number of elements in the list.

2. Heap Operations: The loop iterates over each element in the sorted list and performs heap operations. The heap operations include pushing elements onto the heap and popping the smallest element. In the worst case, each element is pushed onto the heap once, and there are n elements. Therefore, the overall time complexity of heap operations is O(n log k), where k is the maximum heap size.

   • Pushing an element onto the heap has a time complexity of O(log k).
   • Popping the smallest element has a time complexity of O(log k).

3. Total Time Complexity: The overall time complexity is dominated by the sorting operation, making it O(n log n).

Space Complexity:

1. Input Data: The lst list stores the input data, which has a space complexity of O(n).

2. Heap: The heap data structure is used to keep track of the rewards. The space complexity of the heap is O(k), where k is the maximum heap size.

3. Other Variables: The space complexity of other variables is negligible and can be considered O(1).

4. Total Space Complexity: The overall space complexity is O(n + k).

In summary, the time complexity is O(n log n), and the space complexity is O(n + k), where n is the number of elements and k is the maximum heap size.