[BOJ] 17952: 과제는 끝나지 않아!(Python)

17952번: 과제는 끝나지 않아!

문제 설명

과제를 끝냈을 때의 점수와 과제를 완수하는데 걸리는 시간이 주어진다. 과제를 하던 도중 새 과제를 받으면 새 과제를 진행한다고 할 때, 이번 학기에 얻을 수 있는 과제 점수를 구해보자.

나의 풀이

import sys
input=sys.stdin.readline
    
def func():
    n=int(input())
    task=[]
    score=0
    for _ in range(n):
        tmp=input()
        try:
            if tmp[0]=='1':
                _,a,t=map(int,tmp.split())
                task.append([t-1,a])
            if task[-1][0]==0:
                score+=task[-1][1]
                task.pop()
            else:
                task[-1][0]-=1
        except IndexError:
            continue
    return score

print(func())

스택을 사용해 문제를 풀 수 있다. 과제 정보로 1 A T가 주어지면 그 과제를 스택에 삽입한다. 0이 주어지면 현재 스택의 최상위 과제를 수행한다.

시간복잡도

O(n)이다.