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

https://school.programmers.co.kr/learn/courses/30/lessons/176962

프로그래머스

시간 순서에 맞춰 과제를 진행하되, 새로운 과제를 시작할 시간이 된다면, 진행중인 과제를 잠시 중단하고 새로운 과제를 시작한다.

현재 과제 완료 후 멈춰둔 과제가 있다면, 마지막으로 멈춘 과제부터 마저 진행하되, 과제 진행 우선 순서는 새로운 과제가 우선이다.

 

1. 접근

보통 일정과 관련된 문제들은 heap 을 활용하여 진행하는 것이 개인적으로 편해서 heap 을 사용하기로 했고

이 문제의 경우, 멈춰둔 과제를 진행하는 작업이 몇 번이나 반복될지 모르기 때문에 남은 작업 시간을 지속적으로 갱신해야 할 필요가 있다.

 

2. 전처리

일반적으로 일정 관련된 문제가 나오는 경우 int 형식으로 주어지는 문제로 자주 접했으나

이 문제의 경우 시간을 문자열로 입력이 된다. 이 부분을 처리하기 쉽도록 정리해야한다.

또, 과제 정보 (시작 시간, 이름, 완료에 소요되는 시간) 가 시간 순서대로 주어지지 않으므로 정렬이 필요하다.

def solution(plans):
    answer = []
    works = []
    plans.sort(key=lambda x:x[1], reverse=True)
    
    new_plans = []
    index = 1
    for name, start, resource in plans:
        hour, minute = map(int, start.split(":"))
        adjust_time = hour * 60 + minute
        new_plans.append([index, adjust_time, int(resource), name])
        index += 1

먼저 가장 빠른 시간 순으로 처리하기 위해 주어진 plans 리스트를 시간 역순으로 정렬했다.

그 다음으로 시간 정보를 int 형으로 변경하여 계산이 쉽도록 해야했는데,

문제에서 시간은 00:00 ~ 23:59로 날짜를 넘기는 경우가 발생하지 않으므로, 분을 기준으로 통일하기 위해

주어진 시간 정보를 모두 분으로 변경했다. (시간 * 60 + 분)

그 다음, 미뤄진 문제에 대한 우선순위를 정하기 위해 가장 늦은 시간 > 빠른 시간 과제 순으로 index를 넣어줬다

(1, 2 번 과제가 미뤄지면 우선순위는 2번에 있으므로 역순으로 index 부여)

 

3. 처리

while new_plans:
        idx, now, resource, name = new_plans.pop()
        
        if new_plans and new_plans[-1][1] < now + resource:
            resource -= (new_plans[-1][1] - now)
            heapq.heappush(works, [idx, resource, name])
        
        else:
            answer.append(name)
            complete_time = now + resource
    
            while works and new_plans:
                idx, resource, name = heapq.heappop(works)
                
                if complete_time + resource <= new_plans[-1][1]:
                    answer.append(name)
                    complete_time += resource
                    
                else:
                    resource -= (new_plans[-1][1] - complete_time)
                    heapq.heappush(works, [idx, resource, name])
                    break
                    
    while works:
        idx, remain_resource, name = heapq.heappop(works)
        answer.append(name)

new_plans 에서 데이터를 하나씩 뽑아

1. 시작시간 + 소요시간이 다음 과제의 시작 시간보다 늦지 않는다면
    > answer 에 추가 / 현재 시간 = 과제 시작 시간 + 소요 시간

1-1. works 와 new_plans 모두 데이터가 남아있고,
       works 리스트 인덱스 0번의 ( 소요 시간 + 현재 시간 )이 다음 과제 시작 시간보다 늦지 않는다면
      > answer 에 추가 / 1.의 현재 시간 += 소요 시간

1-2. works 와 new_plans 모두 데이터가 남아있고,
       works 리스트 인덱스 0번의 ( 소요 시간 + 현재 시간 )이 다음 과제 시작 시간보다 늦지는다면
      >  ( 다음 과제 시작 시간 - 1.의 현재 시간 ) 만큼 소요 시간에서 차감 후 works 에 추가

2. 시작 시간 + 소요시간이 다음 과제의 시작 시간보다 늦는다면
    > works 에 추가하되, ( 다음 과제 시작 시간 - 현재 과제 시작 ) 만큼 소요 시간에서 차감

3. works 가 남아있다면, 순서대로 뽑아서 answer에 추가

 

4. 최종 코드

import heapq
def solution(plans):
    answer = []
    works = []
    plans.sort(key=lambda x:x[1], reverse=True)
    
    new_plans = []
    index = 1
    for name, start, resource in plans:
        hour, minute = map(int, start.split(":"))
        adjust_time = hour * 60 + minute
        new_plans.append([index, adjust_time, int(resource), name])
        index += 1
        
    while new_plans:
        idx, now, resource, name = new_plans.pop()
        
        if new_plans and new_plans[-1][1] < now + resource:
            resource -= (new_plans[-1][1] - now)
            heapq.heappush(works, [idx, resource, name])
        
        else:
            answer.append(name)
            complete_time = now + resource
    
            while works and new_plans:
                idx, resource, name = heapq.heappop(works)
                
                if complete_time + resource <= new_plans[-1][1]:
                    answer.append(name)
                    complete_time += resource
                    
                else:
                    resource -= (new_plans[-1][1] - complete_time)
                    heapq.heappush(works, [idx, resource, name])
                    break
                    
    while works:
        idx, remain_resource, name = heapq.heappop(works)
        answer.append(name)
        
    return answer