섹션4. 3주차 Stack 백준 2493

1. 현재 학습 진도

• 몇 챕터/몇 강을 수강 중이신가요? 섹션4. 3주차 Stack 3-5

• 어떤 알고리즘을 학습하고 계신가요?

• 여기까지 이해하신 내용은 무엇인가요?

2. 어려움을 겪는 부분

• 딩코님교재 스택부분 예제에 있는 백준 2493 , https://www.acmicpc.net/problem/2493

선생님이 알려준 내용대로 이해하고 제출했으나 3개모두 시간초과가 뜹니다. pypy로 바꿔서도 해봣네용

스택 학습이 우선적이기에 의도했다고 하더라도(제가 잘못 한걸 수도 있습니다!!!1)

시간초과가 뜨지않길 원합니다, 어떻게 코드를 수정해야할까요

3. 시도해보신 내용

• 에러가 발생했다면 어떤 에러인가요? 시간초과

• 현재 작성하신 코드를 공유해주세요

   

 첫번째콛, -내가 작성

n=int(input())

# 한 줄로 입력 받기
data = input().strip()
numbers = list(map(int, data.split()))
result=[]


for i in range(n-1,-1,-1):
    cur_idx=i
    for j in range(i-1,-1,-1):
        if numbers[i]<numbers[j]:
            result.append(j+1)
            break
        elif j==0:
            result.append(0)
result.append(0)

while result:
    print(result.pop(),end=" ")

나머지코드- 딩코님의 작성

n=int(input())

# 한 줄로 입력 받기
data = input().strip()
top_heights= list(map(int, data.split()))

def get_receiver_top_orders(heights):
    answer = [0] * len(heights)
    while heights:
        height = heights.pop()
        for idx in range(len(heights) - 1, -1, -1):
            if height <= heights[idx]:
                answer[len(heights)] = idx + 1
                break
    return answer


print(get_receiver_top_orders(top_heights))  # [0, 0, 2, 2, 4] 가 반환되어야 한다!

n=int(input())

# 한 줄로 입력 받기
data = input().strip()
top_heights= list(map(int, data.split()))


def get_receiver_top_orders(heights):
    answer = [0] * len(heights)
    while heights:
        height = heights.pop()
        for idx in range(len(heights) - 1, -1, -1):
            if height <= heights[idx]:
                answer[len(heights)] = idx + 1
                break
    return answer


print(get_receiver_top_orders(top_heights))  # [0, 0, 2, 2, 4] 가 반환되어야 한다!

이렇게 구체적으로 알려주시면, 더 정확하고 도움이 되는 답변을 드릴 수 있습니다! 😊

def get_receiver_top_orders(heights):
    stack = []  # [인덱스, 높이]를 저장
    answer = [0] * len(heights)
    
    for i in range(len(heights)):
        while stack and stack[-1][1] <= heights[i]:
            stack.pop()
        if stack:
            answer[i] = stack[-1][0] + 1
        stack.append([i, heights[i]])
    
    return answer