[Python] 프로그래머스 Lv.2 과제 진행하기 풀이 및 해석 / 스택을 사용한 알고리즘

문제

 

프로그래머스

 

풀기 전 생각하기 

멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다

이걸 보고서 딱 아 얘는 stack을 사용해야하는구나 생각했다 

멈춘 과제들을 stack에 넣고 후입선출로 마지막에 넣은 과제를 반복문으로 pop()하여 answer에 append 하면되지 않는가...

생각했지만 너무 너무 코드가 복잡해지고... 문법오류에 시달리고 내가 짠 코드가 뭔지도 까먹는 지경에 이르렀다 

아직 코테 감자인 내가 이걸  어찌 시간 안에 어떻게 다 짜

하면서 울다 해당 블로그의 글을 찾았다.... 나는 행복할 수 있었다.....

 

알고리즘 순서 

-과제 시간 int형 변환 후,  오름차순하기

일단 문제가 친절하게 시간 순서대로 주어지지 않더라...^^

시간도 냅다 string으로 줘버린다.....

일단 시간을 split(":")해서 시간 분 나누고 int형으로 바꾸고 h*60+m 해서 바꿔준다

그리고 이걸 sorted해서 오름차순 하여 문제를 풀기 전 상태를 만들어야한다. 

---

- 과제하기

(1) for문을 돌릴건데 i~len(plans)를 돌거다!  i번째 plans 정보를 각각 나눠서 저장할건데

stack에 과제 이름, 소요시간을 넣고 gap에는 지금과제 ~ 다음 과제 사이의 시간을 넣는다  

(2) (1)의 이제 다시 while문을 통해 stack이 비거나  gap이 0일 때까지 반복할거다. 

- i번째 과제의 소요시간이 i+1 과제와의 시간차이보다 작다면! (다음과제 시간 전까지 끝낼 수 있다면)  스택에서 제거하고 answer에다 넣는다 (과제 끝~)

다음 과제까지 남은 시간으로 gap에 입력한다.

While문은 종료된다 

- 다음과제 시간 전까지 끝낼 수 없다면,

일단 멈추고 남은 과제 시간을  계산하고,

gap은 0으로 만들고 (다음 과제 해야하니까...) while문은 종료된다. 

(3) 그리고 다시 1로 돌아가 for문이 끝날때까지 반복한다

(4) answer에 마지막 과제를 넣는다. (마지막 과제까지 다 끝나야 stack에 있는 과제 처리)

(5) stack을 역순을로 answer에 append 한다.  

 

 

정답 코드

 

def solution(plans):
    stack = []
    answer = []

#시간을 int로 바꾼다 
    for i in range(len(plans)):
        h, m = map(int, plans[i][1].split(':')) 
        plans[i][1] = h*60 + m
        plans[i][2] = int(plans[i][2])

    plans.sort(key=lambda x: x[1])

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

        while stack and gap:
            nowTime = stack[-1][1] # 현재 과제의 소요시간
            
            if nowTime <= gap: # 현재 과제의 소요시간이 다음 과제와의 시간차이보다 작다면! (다음과제 시간 전까지 끝낼 수 있다면) 
                name, time = stack.pop() # 스택에서 제거
                gap -= time # 다음과제까지 남은 시간으로 계산
                answer.append(name) # 과제완료!
            else: # 다음 과제시간까지 못 끝내면
                nowTime -= gap # 남은 과제 시간 저장  
                gap = 0 # 다음과제 해야하니까 0

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

    for i in range(len(stack)):
        answer.append(stack[~i][0]) #이렇게 하면 역순으로 append된다

    return answer

 

 

오늘의 배운 것 

#시간을 int로 바꿔꾸는 코드
    for i in range(len(plans)):
        h, m = map(int, plans[i][1].split(':')) 
        plans[i][1] = h*60 + m
        plans[i][2] = int(plans[i][2])

    for i in range(len(stack)):
        answer.append(stack[~i][0]) #이렇게 하면 역순으로 append된다

#람다식 오름차순 내림차순은 왜 맨날 까먹니 
plans.sort(key=lambda x: x[1])

 

 

참고 블로그

https://schini.tistory.com/entry/%EA%B3%BC%EC%A0%9C-%EC%A7%84%ED%96%89%ED%95%98%EA%B8%B0-176962%EB%B2%88-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Programmers