개발/알고리즘

[프로그래머스] 과제 진행

개발자_티모 2023. 5. 7. 04:07
반응형

문제 이해

과제를 끝내는 순서대로 배열에 담아 반환하는 문제입니다. 여러 과제가 주어지는데, 가장 빨리 시작해야 하는 과제부터 선택하여 수행하고, 새로운 과제를 시작할 시간이 되면 기존에 진행 중이던 과제는 멈춥니다. 그리고 현재 수행 중인 과제가 다음 과제의 시작 시간보다 빠르게 끝나면 멈추었던 과제를 이어서 수행합니다. 멈추어 둔 과제를 실행하는 순서는 최신에 멈춘 과제부터 실행합니다.

문제 해결 방법 설명

1. 선택한 과제를 다음 과제를 시작하기 전까지 끝낼 수 있을까?

먼저 초로 단위를 통일했습니다. 해당 초를 정렬해줌으로써 수행하고 있는 과제와 다음에 수행해야하는 과제의 시간을 알아낼 수 있었습니다. 현재 과제의 시작 시간과 과제(A)를 끝내기까지 요구되는 시간(B)과 다음 시작 시간(C)을 알고 있으니 과제의 끝냄과 멈춤을 계산할 수 있을 것입니다(A + B <= C).

 

2. 최근에 멈춘 과제부터 실행할 수 있을까?

최근에 멈춘 과제를 기억하기 위해서 Deque를 사용했습니다. 최근에 멈춘 과제는 pushleft를 수행했고, 다시 과제를 수행할 때는 popLeft를 수행했습니다. 따라서 항상 멈춘 과제부터 실행할 수 있었습니다.

 

코드

def day_to_sec(day):
    time, minute= list(map(int, day.split(":")))
    
    return time * 3600 + minute * 60

def minute_to_sec(min):
    return int(min) * 60
    
def solution(plans):
    from collections import deque
    answer = []
    running_queue = []
    
    waiting_queue = deque()
    
    for plan in plans:
        title, start_time, req_time = plan
        running_queue.append([day_to_sec(start_time), minute_to_sec(req_time), title])
    
    running_queue.sort()
    
    for idx in range(len(running_queue) - 1):
        next_start_time, _, _ = running_queue[idx + 1]
        start_time, req_time, title = running_queue[idx]
        
        
        if start_time + req_time <= next_start_time: #다 끝냄
            answer.append(title)
            
            left_time = next_start_time - (start_time + req_time)
            
            while waiting_queue:
                if left_time == 0:
                    break
                
                left_req_time, left_title = waiting_queue.popleft()
                
                if left_req_time <= left_time:
                    left_time = left_time - left_req_time
                    answer.append(left_title)
                else:
                    waiting_queue.appendleft([left_req_time - left_time, left_title])
                    left_time = 0
        else:                                       #다 못끝냄
            req_time = req_time - (next_start_time - start_time) #남은 시간
            waiting_queue.appendleft([req_time, title])
    
    answer.append(running_queue[-1][2])
                

    while waiting_queue:
        _, title = waiting_queue.popleft()
        answer.append(title)
    return answer



if __name__ == "__main__":
    plans = [["science", "12:40", "50"], ["music", "12:20", "40"], ["history", "14:00", "30"], ["computer", "12:30", "100"]]
    result = ["korean", "english", "math"]
    
    print(solution(plans))

코드 리뷰

def solution(plans):
    plans = sorted(map(lambda x: [x[0], int(x[1][:2]) * 60 + int(x[1][3:]), int(x[2])], plans), key=lambda x: -x[1])

    lst = []
    while plans:
        x = plans.pop()
        for i, v in enumerate(lst):
            if v[0] > x[1]:
                lst[i][0] += x[2]
        lst.append([x[1] + x[2], x[0]])
    lst.sort()

    return list(map(lambda x: x[1], lst))

배운점 정리하기

코드 리뷰의 필자는 과제의 최종 수행 시간을 계산하여 프로그램을 간단하게 작성하였습니다. 반면 저는 A과제가 B과제보다 먼저 끝낼 수 있는지 여부를 계산하고, 불가능한 경우 남은 수행 시간을 큐에 저장하는 방식을 사용하였습니다. 이러한 방식으로 코드를 작성하면, if문의 분기와 남은 과제를 처리하는 로직이 추가로 작성되야 했습니다.

 

또한, 코드 리뷰의 필자는 A과제의 최종 수행 시간을 계산하고, B과제의 시작 시간을 초과한다면 B과제의 해결 시간을 A과제의 최종 수행 시간에 더해주는 방법을 사용하여 2번 조건을 유지하였습니다.

반응형