프로그래머스_과제 진행하기(python)

※ 점근법

 문제에서 시키는 것만 하면 되는 구현 문제이다. 근데 여기서 00:00 ~ 23:59 까지 시간을 흐르게 할지 여부를 정해야 하는데 그러면 오히려 반복 길이가 더 길어질 것 같아서 과제에 들어있는 것을 순차적으로 돌았다.

 

※ 풀이

 1. 일단 멈춘 과제를 담아둘 리스트인 stop을 만들어 줍니다.

 2. 마지막 과제인 경우 후에 처리해야 할 과제가 없기 때문에 무조건 끝내니 이 과제가 마지막인지 여부를 판단해줍니다.

 3. 현재 과제의 끝날 시간과 다음 과제의 시작 시간을 계산해서 비교해줍니다.

 4. 다음 과제 끝날 시간보다 같거나 작은 시간안에 현재 과제가 끝난다면 정답 리스트에 담아줍니다.

 5. 그 후에 멈춰둔 과제가 있다면 진행해줍니다.

 6. 여기서 다음 과제를 할 때까지 남은 시간을 계산해줍니다. (next - temp)

 7. 멈춰둔 과제들을 하나씩 보면서 남은 시간안에 해결할 수 있는 것들을 처리해줍니다.

 8. 깊은 복사로 다시 lis를 stop에 복사시킵니다. 

 9. 과제를 끝까지 다 본 후 멈춘 과제가 있다면 차례대로 결과 리스트에 넣어줍니다.

import copy
def solution(plans):
    answer = []
    stop = []
    plans = sorted(plans, key=lambda x : x[1])
    for i in range(len(plans)):
        if i != len(plans) - 1: # 마지막이 아니라면 
            temp = int(plans[i][1][0:2]) * 60 + int(plans[i][1][3:]) + int(plans[i][2])
            next = int(plans[i+1][1][0:2]) * 60 + int(plans[i+1][1][3:])
            if temp <=next:
                answer.append(plans[i][0]) # 다음 것 안에 끝났으면
                if len(stop) > 0: # 멈춘 것이 있다면
                    lis = copy.deepcopy(stop)
                    tp = next - temp
                    for j in range(len(stop)-1,-1,-1):     
                        if stop[j][1] <= tp:
                            tp -= stop[j][1]
                            answer.append(stop[j][0])
                            lis.pop()
                        else:
                            lis[-1][1] = stop[j][1] - tp
                            break
                    stop = copy.deepcopy(lis)
            else: # 못 끝낸다면
                stop.append([plans[i][0],temp - next])
        else:
            answer.append(plans[i][0]) # 마지막꺼는 걍 끝내면 된다.

    for i in range(len(stop)-1,-1,-1):
        answer.append(stop[i][0])
    return answer

※ 회고

 48, 52, 56점을 맞았을 때 진짜 틀린 것이 없다고 생각을 했다. 구글링을 해볼까도 고민했지만 쭉 알고리즘을 풀면서 맞왜틀이란 없다는 것을 깨달았기에 어디에 반례가 있을지 계속 고민했다. stop 리스트에 문제가 있었던 것을 깨달았고 통과했다. (뿌듯)