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

문제 설명

과제 진행하는 계획

• 과제는 시작하기로 한 시각이 되면 시작
• 새로운 과제를 시작할 시간이 되었을 때, 기존에 진행 중이던 과제가 있다면 진행 중이던 과제를 멈추고 새로운 과제를 시작
• 진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춘 과제를 이어서 진행한다.
  • 만약 과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면, 새로 시작해야 하는 과제부터 진행
• 멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작

문제 풀이 

이 문제를 보고 가장 먼저 든 생각은 스택, 그리고 막대 길이 문제였다. 말로 설명하기 어렵지만 뭔가 이 문제를 막대길이 땅따먹기 ? 하는 방식으로 풀면 되겠다는 생각이 들었다.

스택은 멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작해야 한다는 점에서 생각하게 되었다. 실행중인 과제를 담아놓는 리스트를 만들면 되겠다.

plans 배열 sort

from datetime import datetime

def solution(plans):
    plans.sort(key = lambda x:x[1])
    time_format = "%H:%M"
    start = datetime.strptime(plans[0][1], time_format)
    
    working = []
    answer = []
    
    for p in plans:
        end = datetime.strptime(p[1], time_format)
        p[1] = int((end - start).total_seconds() / 60)
        p[2] = int(p[2])

정답으로 발전시키지 못한 코드이지만, 1차적으로 plans 배열에서 시간 기준으로 sort를 하고, 가장 작은 시작시간 = 0으로 생각하고 각 과제 시작시간의 차이를 변환하여 담았다.

이렇게 변환하여 담았다고 생각하면 된다.

스택 이용하기

working 스택에 현재 실행되는 과제들을 넣어서 관리하려고 했다. 

for i in range(len(plans)-1):
        now = plans[i]
        nextt = plans[i+1]
        if now[2] > nextt[1]:
            now[2] = now[2] - nextt[1]
            working.append(now)
        else:
            answer.append(now[0])

결과

from datetime import datetime

def solution(plans):
    plans.sort(key = lambda x:x[1])
    time_format = "%H:%M"
    start = datetime.strptime(plans[0][1], time_format)
    
    working_stack = [] # 중단된 과제 스택
    answer = []
    current_time = 0
    
    for p in plans:
        end = datetime.strptime(p[1], time_format)
        p[1] = int((end - start).total_seconds() / 60)
        p[2] = int(p[2])
        
    for i in range(len(plans)):
        name, start_time, duration = plans[i]
        
        if i < len(plans) - 1: # 다음 과제가 있을 때
            next_start_time = plans[i + 1][1]  # 다음 과제 시작 시간
            end_time = start_time + duration  # 현재 과제 종료 예상 시간
            
            if end_time > next_start_time:  # 다음 과제 시작 전에 현재 과제가 끝나지 않음 (중단 필요)
                working_stack.append([name, end_time - next_start_time])  # 남은 시간 저장
            else:
                answer.append(name)  # 과제 완료
                current_time = end_time  # 현재 시간 업데이트
                
                # 스택에서 과제 실행: 남아있는 시간이 있을 경우 실행
                while working_stack and (current_time < next_start_time):
                    last_task = working_stack.pop()
                    task_name, remaining_time = last_task
                    
                    if current_time + remaining_time <= next_start_time:
                        current_time += remaining_time
                        answer.append(task_name)  # 완료된 과제 추가
                    else:
                        working_stack.append([task_name, remaining_time - (next_start_time - current_time)])
                        current_time = next_start_time
                        break  # 다음 과제를 시작해야 하므로 중단
        else: # 마지막 과제일 때
            answer.append(name)
            current_time += duration
            
    # 스택에 남아있는 과제 정리
    while working_stack:
        answer.append(working_stack.pop()[0])  # 가장 최근에 멈춘 과제부터 수행
                    
    return answer

스택에 과제가 남아있는 경우를 고려해 주느라 코드가 좀 너무 많아진것 같다..

모범 답안

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))

프로그래머스에서 가장 좋아요를 많이 받은 답안이다. 나의 풀이의 거의 절반이다..