[백준 2493] 탑

초기 실패 코드

n = int(input()) 

tower = list(map(int, input().split())) 

result = []

for i in range(len(tower)):
  if(i == 0):
    result.append(0)
  else:
    flag = False
    for j in range(i - 1, -1, -1):
      if(tower[i] <= tower[j]):
        result.append(j + 1)   # 타워 번호니까 j + 1 추가
        flag = True            
        break
    if(flag == False):
      result.append(0)       # 더 크거나 같은 타워가 없으면 0 추가

타워를 순회할 때 마다 이전 타워 높이들과 비교해서 낮으면 result 배열에 추가하는 방식이다.

하지만 역시나...

N이 50만 이하라는데 뻔한 결과였다.

개선해볼 점

나보다 작은 타워들을 확인해야 하는가?
-> 스택을 사용해 나보다 높거나 같은 타워들은 남기고, 작은 타워들은 제거

최종 코드

n = int(input()) 

tower = list(map(int, input().split())) 

result = []
topStack = []       

# 스택에 만약 나보다 작은 높이가 있다면 전부 제거
# 나를 받아줄건 스택의 가장 위, 없을 수도 있음
# 그 다음 나를 스택에 푸쉬
for i in range(len(tower)):
    while(topStack and topStack[-1][1] < tower[i]):
      topStack.pop()
    if(topStack):
      result.append(topStack[len(topStack) - 1][0] + 1)
    else:
      result.append(0)
    topStack.append([i,tower[i]])

print(" ".join(map(str, result)))

자료구조를 잘 알고 있어야 효율적으로 알고리즘을 짤 수 있을 거 같다