[파이썬] 프로그래머스 : 과제 진행하기 (Lv.2)

[파이썬] 프로그래머스 : 과제 진행하기 (Lv.2)

 

프로그래머스

 

---

풀이

0. 방향성 생각

시작 시간 순으로 오름차순 정렬

덱 맨 앞 2개씩 비교

1. 계획표 정렬

def solution(plans):
    
    prep,done,remain = [],[],[]
    for name,start,playtime in plans:
        prep.append([name,60*int(start[:2])+int(start[-2:]),int(playtime)])
    prep.sort(key=lambda x:x[1])

시간은 모두 분 단위 정수로 변경하고 오름차순 정렬한다.

 

2. 덱 만들기

    q = deque(prep)
    time = q[0][1]
    while len(q)>=2:
        
        sub,start,playtime = q.popleft() # q1
        nsub,nstart,nplaytime = q.popleft() # q2

덱에서 2개씩 뽑아서 비교한다.

맨 앞을 q1, 그 뒤가 q2

2-1. q1이 끝나지 않는 경우

        if start + playtime > nstart : # q1 안끝나는 경우
            remain.append([sub,start,playtime-(nstart-start)]) # 잔업은 스택에
            q.appendleft([nsub,nstart,nplaytime]) # 다음 할일은 다시 큐 앞에
            time = nstart

q1이 끝나지 않는 경우에 실행시간 nstart-start를 playtime에서 빼준 후 remain에 넣어준다.

q2는 덱의 맨 앞에 추가한다.

현재 시각은 다음 과제가 실행되는 nstart

2-2. q1이 끝나고 바로 q2 실행되는 경우

        elif start + playtime == nstart : # q1 끝나고 바로 q2
            done.append(sub)
            q.appendleft([nsub,nstart,nplaytime])
            time = nstart

q1을 마쳤으니 done에 추가

q2는 덱의 맨 앞에 추가.

현재 시각은 다음 과제가 실행되는 nstart 

2-3. q1이 끝나고 q2 까지 텀이 있는 경우

        else : # q1 끝나고 q2까지 텀 있는 경우
            done.append(sub)
            q.appendleft([nsub,nstart,nplaytime])
            time = start + playtime
            while remain :
                if time == nstart :
                    break
                rsub,rstart,rplaytime = remain.pop()
                if time + rplaytime <= nstart : # 잔업 하나 끝낼 수 있으면 반복
                    done.append(rsub)
                    time += rplaytime
                else :
                    remain.append([rsub,rstart,rplaytime-(nstart-time)])
                    break

이 경우는 q1을 마치고 스택에 과제가 있는지 확인하면 된다.

스택 remain에 과제가 있을 경우 remain의 맨 위에서 빼서 확인한다.

만약 q2 시작 전에 처리가 가능한 경우 처리한다.

done에 잔업 rsub를 추가해주고 시각은 time + rplaytime으로 업데이트한다.

끝낼 수 없으면 텀동안 잔업을 실행하고 남은 시간을 업데이트 하고 다시 스택의 맨 위에 넣는다.

 

만약 time == nstart가 되면 다음 잔업보다 우선순위가 높은 q2를 실행해야 하므로 탈출한다.

 

3. 잔업 처리

   sub,start,playtime = q.popleft()
    done.append(sub)
    for sub,start,playtime in remain[::-1]:
        done.append(sub)
        
    return done

덱에 남은 마지막 업무를 추가하고 스택의 맨 위부터 done에 추가해준다.

---

전체코드

from collections import deque

def solution(plans):
    
    prep,done,remain = [],[],[]
    for name,start,playtime in plans:
        prep.append([name,60*int(start[:2])+int(start[-2:]),int(playtime)])
    prep.sort(key=lambda x:x[1])

    q = deque(prep)
    time = q[0][1]
    while len(q)>=2:
        
        sub,start,playtime = q.popleft() # q1
        nsub,nstart,nplaytime = q.popleft() # q2
        
        if start + playtime > nstart : # q1 안끝나는 경우
            remain.append([sub,start,playtime-(nstart-start)]) # 잔업은 스택에
            q.appendleft([nsub,nstart,nplaytime]) # 다음 할일은 다시 큐 앞에
            time = nstart
            
        elif start + playtime == nstart : # q1 끝나고 바로 q2
            done.append(sub)
            q.appendleft([nsub,nstart,nplaytime])
            time = nstart
            
        else : # q1 끝나고 q2까지 텀 있는 경우
            done.append(sub)
            q.appendleft([nsub,nstart,nplaytime])
            time = start + playtime
            while remain :
                if time == nstart :
                    break
                rsub,rstart,rplaytime = remain.pop()
                if time + rplaytime <= nstart : # 잔업 하나 끝낼 수 있으면 반복
                    done.append(rsub)
                    time += rplaytime
                else :
                    remain.append([rsub,rstart,rplaytime-(nstart-time)])
                    break
                    
    sub,start,playtime = q.popleft()
    done.append(sub)
    for sub,start,playtime in remain[::-1]:
        done.append(sub)
        
    return done

코멘트

처음에 바로 짜서 45~65점만 계속 나왔는데 못넘었는데 다시 분기문 잘 짜서 합격.

구현이 살짝 까다롭네요