백준 2493 탑

처음 나의 답

시간초과가 났다.
하긴 탑이 500,000개 있는데 사실상 포문 두번 돌린거라 이상할게 없긴했다..

length = int(input())
lines = list(map(int, input().split()))

stack = [lines[0]]
res = [0]


def findBiggerIdx(curHeight):
    for i in range(len(stack) - 1, -1, -1):  # 스택 역순 조회
        if stack[i] >= curHeight:
            return i + 1
    return 0


for i in range(1, len(lines), 1):  # 1번 인덱스부터 조회
    cur = lines[i]
    bigger = findBiggerIdx(cur)
    res.append(bigger)
    stack.append(cur)

print(*res, sep=" ")

답

우선 인터넷에서 구상하는 방법을 살펴보고, 천천히 구현해보니 해결되었다.

length = int(input())
lines = list(map(int, input().split()))

stack = []
res = []

for i in range(length):
    while stack:
        if stack[-1]['val'] < lines[i]:
            stack.pop()
        else:
            res.append(stack[-1]['idx'] + 1)
            stack.append({'idx': i, 'val': lines[i]})
            break
    if not stack:
        stack.append({'idx': i, 'val': lines[i]})
        res.append(0)

print(*res, sep=" ")

우선 인덱스 값과 탑의 높이를 담을 딕셔너리를 생각해야한다.
우리가 찾아야하는 값은 인덱스 + 1 이기 때문

쨌든 스택에는 의미있는 탑들만 들어간다.

1. 탑 리스트를 돈다
2. 스택이 비어있지 않다면, 스택의 마지막 값에서 탑의 높이를 본다
3. 현재 보고 있는 탑보다 크다면 멈추고, 정답 배열에 해당 스택의 인덱스 + 1 을 담아준다.
4. 현재 보고 있는 탑보다 작다면, 해당 딕셔너리를 스택에서 pop한다.
5. 만약 스택을 끝까지 다 돌며 모두 pop 했는데 (내가 제일 큰 경우) 없다면 반복문을 탈출하게 된다.
6. 반복문을 탈출해서 스택이 비어있는 경우, 스택에 현재 탑 정보를 담아준다.

위 방법으로 구현했다.