UNIST, CSE 3th

1 minute read

1834. Single-Threaded CPU (medium)

heap을 이용하자…. 제발… 어제봤었던건데 그걸 못 써먹고 있으니 참 문제가 많다 나도. heapq.heappush(heap, (pt, idx, st)) 에서 가장 첫번쨰 element로 process_time 을 이용해서 shortest processing time 을 가진 process를 뽑는데 이용했다. heap이라서 가장 작은 element를 추출하는데 O(log n) 이 소요되어서 결국 전체 time complexity 는 O(n log n) 이 된다. 아래 코드는 내가 멍청하게 list를 이용해서 문제를 풀었던 것인데 get_shortest 같은 적당한 process를 추출하기 위한 뻘짓들(?)이 적나라하게 나타나고 있다.

class Solution:

    def get_shortest(self, tasks):
        index = 0
        for i, task in enumerate(tasks):
            if tasks[i][1] < tasks[index][1]:
                index = i
            elif tasks[i][1] == tasks[index][1]:
                if tasks[i][2] < tasks[index][2]:
                    index = i
        return (index, tasks[index])


    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        # sort with enqueue time and index the tasks
        n = len(tasks)
        for i, task in enumerate(tasks):
            task.append(i)
        tasks.sort(key=lambda x : x[0])

        res = []
        avail = []
        current = tasks[0][0]
        check = [False] * n
        check_num = 0
        while check_num < n:
            for i, task in enumerate(tasks):
                if not check[i] and task[0] <= current:
                    avail.append(task)
                    check[i] = True
                    check_num += 1
            # print(avail)
            index, process = self.get_shortest(avail)
            res.append(process[2])
            current += process[1]
            avail.pop(index)

        while len(avail) > 0:
            index, process = self.get_shortest(avail)
            res.append(process[2])
            current += process[1]
            avail.pop(index)
        return res

heap을 이용한 풀이, 나중에 python에서 어떻게 heap을 이용하는지 찾아봐야겠다. 여기서는 heapq를 import해서 사용하고 있는데, 다른 library들이 있는지, 다른 사용방식이 있는지 찾아봐야겠다.

import collections
import heapq
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        lookup = collections.defaultdict(list)
        for idx, (st, pt) in enumerate(tasks):
            lookup[st].append((pt, idx, st))
        heap, ans, last = [], [], 0
        for t in sorted(lookup):
            while heap and last < t:
                pt, idx, st = heapq.heappop(heap)
                last = max(st, last) + pt
                ans.append(idx)
            for pt, idx, st in lookup[t]:
                heapq.heappush(heap, (pt, idx, st))
        while heap:
            ans.append(heapq.heappop(heap)[1])
        return ans

You may also enjoy