[스택] (프로그래머스_176962) 과제 진행하기 (☆☆☆)

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

 

📌 총평: 구현이 좀 까다로운 조건들이 있어서 어려웠다.

우선 gap을 이용해서 추가적으로 stack안에 있는 과제들을 진행할 수 있는지를 구현하는게 주 아이디어였다.

그리고 이후에 i,i+1을 이용해 gap을 구했기때문에 맨마지막 plans[-1]을 답에 넣어줘야했다.

마지막에 stack에 남아있는 것들을 거꾸로 꺼내서 답에 넣어야한다는 것도 바로 떠올리기 어려웠다.

 

📌 문제 이해:

과제를 받은 루는 다음과 같은 순서대로 과제를 하려고 계획을 세웠습니다.
과제는 시작하기로 한 시각이 되면 시작합니다. (우선적으로 과제를 시간 순 정렬 해야함)
새로운 과제를 시작할 시각이 되었을 때, 기존에 진행 중이던 과제가 있다면 진행 중이던 과제를 멈추고 새로운 과제를 시작합니다.
(새로운 과제 우선 -> for문으로 새로운 과제를 주고 진행중인 과제 stack에 넣기 ; stack에 넣을때는 과제 시간에서 진행된 시간을 빼주고 넣어야함 )
진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행합니다.
만약, 과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면, 새로 시작해야 하는 과제부터 진행합니다.
(과제가 끝나고  stack을 들여다볼건데 만약 gap-=playtime-> gap=0이면 새로운 과제부터 진행 )
멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다.
(stack.pop())
과제 계획을 담은 이차원 문자열 배열 plans가 매개변수로 주어질 때, 과제를 끝낸 순서대로 이름을 배열에 담아 return 하는 solution 함수를 완성해주세요.

 

📌 알고리즘

1️⃣ 과제 시작시간, 소요시간이 문자열이므로 int로 변환 후  과제 시작시간순으로 정렬

def solution(plans):
    def convert_int(string):
        h,m=map(int,string.split(":"))
        return h*60+m
        
    for i in range(len(plans)):
        plans[i][1]=convert_int(plans[i][1])
        plans[i][2]=int(plans[i][2])
    
    plans.sort(key=lambda x:x[1])

 

2️⃣ 과제 시작 순으로 for문 돌림, 다음 과제까지의 gap을 계산하고, stack에 지금 주어진 과제를 넣어서 먼저 처리되도록함

    answer = []
    stack=[]
    for i in range(len(plans)-1):
        gap = plans[i+1][1]-plans[i][1]
        stack.append([plans[i][0],plans[i][2]]) #task_name,task_time

 

3️⃣ 이후 gap>0 (과제를 수행할 수 있으면)이고 stack이 있을때까지 stack에서 가장 최신 과제를 꺼냄

        while gap>0 and stack:
            task_name,task_time = stack.pop()

 

4️⃣ 만약 현재 과제를 수행가능한 시간인 gap과 과제 소요시간 task_time을 비교했을 때  충분히 과제를 끝낼 수 있으면 (task_time<=gap) 과제를 끝내고 답 배열 안에 과제 이름을 넣음, 그리고 gap을 수행시간만큼 빼줌 (gap-=task_time)

            if task_time<=gap:
                answer.append(task_name)
                gap-=task_time

 

5️⃣ 만약 과제소요시간이 수행가능시간보다 크면 (task_time>gap) 중간에 끝내고 새로운 과제를 시작해야하므로, stack에 과제소요시간에서 수행가능시간을 뺀시간(task_time-gap)으로 넣어주고 gap=0으로 초기화해줘서 수행가능시간을 없다고 명시해줌

            else:
                stack.append([task_name,task_time-gap])
                gap=0

 

6️⃣ for문 범위가 range(len(plans)-1)이므로 마지막 과제를 답에 넣어줌

    answer.append(plans[-1][0])

 

7️⃣ 마지막으로 stack에 남아있는 과제들을 담아줌 [~i]는  i + 1에 음수 부호를 붙인 값 넣는다는 뜻임 ex) 0-> -1

    for i in range(len(stack)):
        answer.append(stack[~i][0])
    
    return answer

 

📌 전체 코드

def solution(plans):
    def convert_int(string):
        h,m=map(int,string.split(":"))
        return h*60+m
        
    for i in range(len(plans)):
        plans[i][1]=convert_int(plans[i][1])
        plans[i][2]=int(plans[i][2])
    
    plans.sort(key=lambda x:x[1])
    answer = []
    stack=[]
    for i in range(len(plans)-1):
        gap = plans[i+1][1]-plans[i][1]
        stack.append([plans[i][0],plans[i][2]]) #task_name,task_time
        while gap>0 and stack:
            task_name,task_time = stack.pop()
            if task_time<=gap:
                answer.append(task_name)
                gap-=task_time
            else:
                stack.append([task_name,task_time-gap])
                gap=0
                
    answer.append(plans[-1][0])
    
    for i in range(len(stack)):
        answer.append(stack[~i][0])
    
    return answer