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

1차시도

처음에는 브루트포스 처럼 풀었다.
리스트로 탑 쭉 입력받고 for문 돌리면서 수신받을 수 있는 탑 하나씩 찾는 형식으로 풀었다.

당연히 시간초과 오류 발생

2차시도

시간초과를 줄이려고 많은 시도를 해보았다.
1. maxTower 변수를 통하여 가장 높은타워를 기억하고 있다가 더 높은타워가 나오면 바로 0기록하고 스킵
2. savedTower 딕셔너리 추가해서 이전 탑과 다음탑의 높낮이 비교, 높고낮음을 분기하여 for문 돌리지 않고 바로바로 저장할 수 있도록 로직처리
3. 정말 마지막 예외케이스만 for문 돌리게 구현한게 아래의 코드다.

import sys

N = int(sys.stdin.readline())
towers = list(map(int, sys.stdin.readline().split()))
answer = list()
maxTower = 0
savedTower = {'idx' : 0, 'value' : 0}

for i in range(N):
    if maxTower < towers[i]:
        answer.append(0)
        maxTower = towers[i]
        continue
    if towers[i] <= towers[i-1]:    # 다음탑이 이전탑보다 작거나 같은경우
        answer.append(i)            # 이전 탑 인덱스 기록
        savedTower['idx'] = i-1         # 최근에 가장 높았던 탑 기록
        savedTower['value'] = towers[i-1]
        continue
    else:   # 다음탑이 이전탑보다 높은 경우
        if towers[i] <= savedTower['value']:
            answer.append(savedTower['idx'] + 1)
            continue
        else:
            for num in range(i - savedTower['idx'], i+1):
                if towers[i] <= towers[i-num]:
                    answer.append(i-num+1)
                    break
        # if num == i:
        #     answer.append(0)
        #     break

print(answer)

역시 시간초과가 떴다.

3차시도

자료구조 문제라는걸 간과하고 있었다.
2차시도에서 했던 방식은 브루트포스 방식에서 스택사용방식으로 가는 과정을 어설프게 따라한거같다.
어설프게 maxTower, savedTower 같은 변수로 이전의 상태를 저장하려 했지만, Stack을 사용할 경우 이 모든 과정이 깔끔하게 해결되었다.

스택을 사용해서 이전 타워와 비교할 수 있도록 코드를 아예 다시 짜보았다.

0. 기본적으로 매 차시 진행마다 스택에 본인 탑 인덱스를 넣고 다음으로 진행함
1. 스택이 비어있으면 더이상 앞쪽에 큰 탑이 없기 때문에 0 출력하고 다음으로 진행
2. 스택이 비어있지 않으면, 스택의 가장마지막 탑과 현재 탑 비교
   2-1. 현재탑이 더 크면 스택에서 pop해서 없애버림 (더이상 오른쪽의 탑을 수신할 수 없기 때문)
   2-2. 현재탑이 더 작으면 스택의 마지막 탑이 수신가능한 탑이므로 정답 출력 후 다음으로 진행 (pop해서 없애지 않음)

import sys

N = int(sys.stdin.readline())
towers = list(map(int, sys.stdin.readline().split()))
answer = list()
towerStack = list()


for i in range(N):
    # 예외적인 케이스 (맨 처음에 스택이 0 상태인 경우)
    if len(towerStack) == 0:        # 스택에 아무것도 없으면 더이상 앞에 큰 타워가 없으니까 0 출력넣고 스택에 본인 넣음
        answer.append(0)
        towerStack.append(i)
        continue
    else:
        # 일반적인 케이스 (수신할 수 있는 타워를 찾는 경우)
        while towers[towerStack[-1]] < towers[i]:   # 스택 내에서 수신가능한 타워를 찾는 과정
            towerStack.pop()
            if len(towerStack) == 0:                # 탐색중 스택이 비어버린 경우 (수신 가능한 타워가 없음)
                answer.append(0)
                towerStack.append(i)
                break
    if towerStack[-1] == i:                         # while문 break로 빠져나오고 continue 바로 하기 위한 조건문
        continue
    answer.append(towerStack[-1] + 1)               # 수신가능한 타워를 while문에서 정상적으로 찾은 경우 정답 출력
    towerStack.append(i)

print(*answer)

그냥 자료구조 잘 선정해서 쓰면 간단하게 풀리는 문제였다.
설계할 때 풀이방식이나 알고리즘보다 자료구조를 우선적으로 생각해보면 좋을것 같다고 생각하게된 계기였다.