[알고리즘 문제 풀이][파이썬] 프로그래머스: 과제 진행하기

프로그래머스 과제 진행하기 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/176962

📑 문제 설명
1. 입력으로 과제명, 시작시간, 소요시간 이 들어온다.
2. 과제는 시작할 시간이 되었을 때 시작한다.
3. 새로운 과제를 시작할 시간에 진행중이던 과제가 있다면 과제를 멈추고 새로운 과제를 시작한다.
4. 진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면 멈춰둔 과제를 이어서 진행한다. --> 새로 시작해야 되는 과제와 잠시 멈춘 과제가 있다면 새로 시작해야 되는 과제 먼저 진행한다.
5. 멈춰 둔 과제가 여러 개일 경우 가장 최근에 멈춘 과제부터 시작한다.(Stack)

입력: [과제명, 시작 시간, 소요 시간]
출력: [과제를 완료한 순서대로 과제명 나열]

💡 문제 해결 방법
알고리즘: 구현 문제, stack 자료 구조 사용

1. 스트링으로 구성된 시작 시간과 소요 시간을 처리해주어야 함.
2. 과제 순서는 랜덤으로 섞여서 입력되기 때문에 정렬해야 함.
3. 과제를 시간 순서대로 처리할 때 다음과 같은 예외 처리 필요.
   3-1. 진행중이던 과제가 시간 내에 완료할 경우
   answer 리스트에 진행중이던 과제 추가
   3-1-1. 진행중이던 과제를 하고 나서도 시간이 남을 경우
   stack에 가장 최근에 저장된 과제를 진행
   - 과제를 완료했을 경우 answer list에 추가
   - 과제를 완료하지 못했을 경우 남은 시간을 수정하여 stack에 추가
   3-2. 진행중이던 과제를 시간 내 완료를 못할 경우
   stack에 과제 및 잔여 시간을 추가
4. 가장 마지막 시간에 진행하는 과제는 stack에 추가
5. 남은 과제가 존재할 경우, 마지막 원소부터 출력하여 완료

예외처리 및 추가 내용
1. 시작 시간을 어떻게 처리할 지 고민
- 스트링이기 때문에 인트형으로 변환
- 00:00~23:59 이므로 분으로 변환하여 연산을 진행하면 60분을 고민하지 않고 해결할 수 있음
2. 연산할 시간이 많기 때문에 구분 잘하여 진행하기
- 다음 과제 시작 시간 - 진행 중인 과제 시작 시간
- (진행중이던 과제 완료 후) 다음 과제 시작 시간 - 진행 중인 과제 마친 시간
- 공백 시간을 연산해야 멈춰둔 과제 진행 여부 파악 가능
- (다음 과제 시작 시간 - 진행 중인 과제 마친 시간) - 멈춰둔 과제 잔여 시간
- 진행중이던 과제 잔여 시간

💻 코드

def solution(plans):
    answer = []
    for i in range(len(plans)):
        h, m = map(int, plans[i][1].split(':'))
        st = h*60+m
        plans[i][1] = st
        plans[i][2] = int(plans[i][2])
        
    plans.sort(key=lambda x:x[1])
    stack = []
    for i in range(len(plans)):
        if i == len(plans)-1:
            stack.append(plans[i])
            break
        
        sub, st, t = plans[i]
        nsub, nst, nt = plans[i+1]
        if st + t <= nst:
            answer.append(sub)
            temp_time = nst - (st+t)
            
            while temp_time != 0 and stack:
                tsub, tst, tt = stack.pop()
                if temp_time >= tt:
                    answer.append(tsub)
                    temp_time -= tt
                else:
                    stack.append([tsub, tst, tt - temp_time])
                    temp_time = 0
            
        else:
            plans[i][2] = t - (nst - st)
            stack.append(plans[i])
        
    while stack:
        sub, st, tt = stack.pop()
        answer.append(sub)

    return answer

💟 추가적으로 알게 된 점
1. 내가 생각한 알고리즘대로 풀고 싶어서 고민을 많이 부렸던 문제
2. 역시 해결 도우미는 질문 게시판 반례 찾기...
3. 시간 연산이 나를 괴롭힘

참고
https://school.programmers.co.kr/questions/46749