2493번 탑

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

---

아이디어

17928번 오큰수 문제와 아이디어와 코드가 너무 비슷하다.
+) 만약 이 문제를 풀었다면 바로 오큰수 도전해보는 것도 좋을 것 같다.

이 문제의 아이디어는 스택을 이용하여 top보다 숫자가 크거나 같으면 pop하고, top보다 숫자가 작으면 answer을 top 숫자의 인덱스로 갱신하고 해당 숫자를 push 해야한다.
이때 stack에 넣을 때 두 가지 원소를 튜플로 한 번에 넣었는데 (i, j)를 넣었다고 가정하면 i는 value, j는 주어진 입력에서 i(value)의 인덱스 값이다.

사실 이 문제는 3달 전에 풀었던 문제인데 이때와는 아이디어는 똑같지만 코드 구성이 달라서 둘이 비교하는 재미가 있다. 뭔가 오늘 푼 코드가 더 개선된 느낌이다.
1번 코드가 최근 코드, 2번 코드가 3달 전 코드이다.

---

코드

1

n = int(input())
l = list(map(int, input().split()))

stack = []
answer = [0]*n

for i in range(n):
    while stack and stack[-1][0] <= l[i]:
        stack.pop()
    if stack:
        answer[i] = stack[-1][-1]+1
    stack.append((l[i], i))
print(*answer)

2

n = int(input())
l = list(map(int, input().split()))

stack = []
answer = [0] * n
for i in range(n):
    while stack:
        if stack[-1][1] > l[i]:
            answer[i] = stack[-1][0] + 1
            break
        else:
            stack.pop()
    stack.append((i, l[i]))
print(*answer)