[백준 파이썬] 2493번 탑

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

2493번: 탑

 

<코드>

 

1. 통과

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
stack = []
result = [0]*n

for i in range(n-1, -1, -1):
    while True:
        if stack and stack[-1][0] < arr[i]:
            value, idx = stack.pop()
            result[idx] = i+1
        else:
            break
    stack.append((arr[i], i))
print(*result)​

 

2. 시간초과

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
result = [0]
for i in range(1, n):
    for j in range(i-1, 0, -1):
        if arr[j] >= arr[i]:
            result.append(j+1)
            break
    else:
        result.append(0)

print(*result)

 

<풀이방법>

2중 for문으로 나보다 높은거 찾으면 idx값 넣고 break했는데.. 시간초과남

stack으 오른쪽부터 시작해서 스택 젤 마지막 값보다 지금 값이 더 크면 pop하고  result의 해당 인덱스에 지금 인덱스 넣어주고 반복해준다.