알고리즘 풀이

입출력

• 입력
  5 6 9 5 7 4

• 출력
  0 0 2 2 4

문제 설명

일직선 위에 n개의 높이가 서로 다른 탑을 차례로 세운다. 꼭대기에 레이저 설치
오른쪽에서 어느 탑이 레이저 쏘면 왼쪽에 있는 가장 가까우면서 자신보다 더 높은 탑이 받음 각 탑이 레이저 받는 개수를 출력

1차

배열을 그대로 스택에 넣었다가 더 작은건 pop하고 찾으면 break 하는 방식으로 진행했더니 시간초과 발생

from collections import defaultdict

N = int(input())
tops = list(map(int, input().split()))
answer = []

for i in range(N-1, -1, -1):
    nowTop = tops[i]
    tmp = tops[:]

    while tmp[-1] != nowTop:
        tmp.pop()
    
    tmp.pop()
    flag = False
    for j in range(i, 0, -1):
        if tmp[-1] > nowTop:
            answer.insert(0, j) 
            flag = True
            break
        tmp.pop()
    if flag == False:
        answer.insert(0, 0)
print(answer)

2차

포인트는 최소한의 반복문을 돌아야한다는 것이다.
따라서 스택에 [index, value]를 함께 넣어주어서 값을 비교할때는 1번째 값을, 실제로 답을 넣을 때는 0번째 값을 넣어야 했다.

실제로 풀이한 방식은 끝값부터 스택에 넣는다. 원하는 i 값보다 큰 값을 찾으면 스택에서 빼서 정답 배열에 위치에 따라 자신의 인덱스를 넣는다. 그러고 나와서 자기 자신을 넣고 반복한다.

N = int(input())
tops = list(map(int, input().split()))
stack = []
answer = [str(0) for _ in range(N)]

for i in range(N-1, -1, -1):
    if len(stack) == 0:
        stack.append([i, tops[i]])
    else:
        while tops[i] > stack[len(stack)-1][1]:
            nowTop = stack.pop()
            answer[nowTop[0]]= str(i+1)
            if len(stack) == 0:
                break
        stack.append([i, tops[i]])
print(" ".join(answer))