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

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

시작 시간과 필요 시간이 주어진 과제 리스트가 있고, 과제를 진행하는데 다른 과제 시작할 시간이 되면 잠시 멈추고 다른 과제 하고 뭐 그런 식으로 진행했을 때 완료되는 순서를 출력하는 문제이다.

먼저, 과제의 시간이 hh:mm으로 주어지는데 이거를 hh * 60 + mm으로 변환하고 내림차순으로 정렬했다.

keep이라는 배열을 하나 만들어서 잠시 멈춘 과제를 저장하도록 했다.

그래서 plans 리스트와 keep리스트에 원소가 있는 동안 현재 시간이 plans의 제일 마지막 과제의 시작시간이면 그거 먼저 처리하고, 처리하다가 다른 과제 할 시간이 되면 잠시 멈추고 남은 시간을 저장했다.

시간이 비면 남은 과제 처리하게 했는데 시간초과로 실패했다.

def solution(plans):
    answer = []
    
    for i, p in enumerate(plans):
        h, m = map(int, p[1].split(":"))
        plans[i] = [p[0], 60 * h + m, int(p[2])]
        
    plans.sort(key=lambda x:(-x[1]))
    
    keep = []
    
    time = plans[-1][1]
    while plans or keep:        
        if plans and time >= plans[-1][1]:
            now = plans.pop()
        elif keep:
            now = keep.pop()
            
        answer.append(now[0])
        time = now[1] + now[2]
        
        if plans and time > plans[-1][1]:
            answer.pop()
            rest = time - plans[-1][1]
            keep.append([now[0], plans[-1][1], rest])
            time = plans[-1][1]
        
    
    return answer

첫 if-elif 문에서 시간이 빌 때 즉 keep에 작업 없고, plans의 다음 작업 시간이 아직 안 됐을 때 어떻게 해야할 지 지정해주지 않아서 시간 초과가 발생한 것이었다.

elif plans:
	now = plans.pop()

이라는 구문을 추가해주니까 시간초과는 발생하지 않았는데, 몇몇 테스트케이스에서는 실패했다.

해결

def solution(plans):
    answer = []
    
    for i, p in enumerate(plans):
        h, m = map(int, p[1].split(":"))
        plans[i] = [p[0], 60 * h + m, int(p[2])]
        
    plans.sort(key=lambda x:(-x[1]))
    
    keep = []
    
    time = plans[-1][1]
    while plans or keep:
        if plans and time >= plans[-1][1]:
            now = plans.pop()
        elif keep:
            now = keep.pop()
        elif plans:
            now = plans.pop()
            time = now[1]

        answer.append(now[0])
        time += now[2]
        
        if plans and time > plans[-1][1]:
            answer.pop()
            rest = time - plans[-1][1]
            keep.append([now[0], plans[-1][1], rest])
            time = plans[-1][1]
        
    
    return answer

time을 매번 now[1] + now[2]로 업데이트 해주는 데서 문제가 발생했다.
keep에는 작업이 중단된 시간을 저장하도록 했는데, 이거 때문에 다른 작업 하고 시간이 한참 지났다가 keep의 작업을 하게 되면 time이 되돌아가는 문제가 발생했다.
그래서 그냥 time에는 진행했던 시간만 더하도록 했다.
이렇게 하니까 다른 문제는 keep의 작업도 없고, plans에 시간도 아직 안 됐을 때 plans에서 억지로 꺼내서 작업을 하게 했는데 time은 그대로라서 문제가 있었다. 그래서 억지로 꺼낼 때는 time도 업데이트 하도록 했다.