2493 백준 파이썬

꽤나 중요한 것을 배웠던 문제

아래는 시간초과 났던 코드이다.

n=int(input())
l=list(map(int,input().split()))
result=[0 for x in range(n)]
for x in range(len(l)):
    stack=l[:x+1]
    now=stack.pop()
    t=0
    cnt=0
    while t<now and stack:
        t=stack.pop()
        cnt+=1
    result[x]=x-cnt
for x in range(len(result)):
    if result[x]!=0:
        result[x]+=1
result=map(str,result)
print(" ".join(result))

stack을 슬라이싱으로 받았고, 그에 따라 시간복잡도가 O(N^2)이 되어 시간 초과가 나타났다.

 

아래는 정답코드이다.

stack에 위치를 기록해주고, break문으로 적절히 끊어준다. 이러면 시간복잡도가 O(N)이 된다.

n=int(input())
l=list(map(int,input().split()))
result=[0 for x in range(n)]
stack=[]
for x in range(n):
    while stack:
        if stack[-1][1]>l[x]:
            result[x]=stack[-1][0]+1
            break
        else:
            stack.pop()
    stack.append([x,l[x]])
result=map(str,result)
print(" ".join(result))

코드 구조와 별개로 시간복잡도가 달라질 수 있다는 것을 배웠다.

조금더 파봐야 하겠지만 꽤나 흥미롭다.