[Python] 백준 2493 탑

https://www.acmicpc.net/problem/2493

2493번: 탑

문제분석

탑이 있고, 그 탑의 꼭대기에서 <<< 좌측으로 레이저 발사.

이 레이저가 가장 먼저 닿는 탑이 몇번째 탑인지 각 탑마다 확인 후,,모든 탑의 값을출력

해결과정

1차 코드:시간복잡도 N^2(시간초과.시간초과.시간초과.)

#브루투 포스(완전 탐색)
for i in range(n):#레이저 쏘는 기둥
    for k in range(i,-1,-1):#레이저 어느기둥이 맞는지 확인, k번째면 k를 result[i]에 저장
        if arr[i]<arr[k]:
            if k+1 in result:
                if arr[result.index(k+1)]!=arr[i] and result[i]==0:#저장된 k+1의값이 있는 기둥의 높이와 i기둥의 높이가 다를경우
                    result[i]=k+1
                    break
                elif result[i]==0:#같을경우+안에 값이 없을 경우(있는경우냅두기)
                    result[i]=0
            elif result[i]==0:#비어있으면 넣기(안비어있으면 넣으면안됨)
                result[i]=k+1
                break
    for i in range(len(result)):
        print(result[i],end=' ')

채점결과

PyPy3까지 시간초과가 떠서 접근이 잘못되었다는것을 느낌. 힌트를 보니 '스텍'이 써있길래 스텍으로 구현하려 했다.

2차 코드: 스텍 이용(또 시간초과...)

# 스텍 구조 활용-실패
n=int(input())
arr=[]
arr=list(map(int,input().split()))
result=[0]*n
stack=[]
for i in range(1,n):
    stack.append([arr[i-1],i])#스텍 앞부분이 기둥높이
    while len(stack)!=0:
        if arr[i]<stack[-1]:
            result[i]=arr.index(stack[-1])+1  
            break
        else:
            stack.pop()
print(*result)

스텍구조를 이용하였고, 정말 잘 한거같은데도 이상하게 자꾸 시간초과가 뜨길래...시간을 잡아먹는걸 최대한 찾았다.

다른 부분은 다른사람들이 한것과 거의 같아서 놔두고, 혹시 arr.index()로 인덱스 찾아오는게 시간복잡도를 먹나?

3차 코드: 스텍 이용(최적화..최적화...)

n=int(input())
arr=[]
arr=list(map(int,input().split()))
result=[0]*n
stack=[]
for i in range(1,n):
    stack.append([arr[i-1],i])#스텍 앞부분이 기둥높이, 뒷부분이 기둥인덱스+1
    while len(stack)!=0:
        if arr[i]<stack[-1][0]:
            result[i]=stack[-1][1] 
            break
        else:
            stack.pop()
print(*result)

그래서 스텍구조를 살짝 바꿔서, 인덱스를 스텍에서 찾아오게끔 했다. 이렇게 하니 통과되더라.