섹션4. 3주차 Stack 백준 2493

Question

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] 가 반환되어야 한다!

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

딩코딩코 · Answer

안녕하세요 zz gg 님 좋은 질문 감사드립니다!

해당 문제 풀이의 경우 말씀해주신대로 시간 초과가 발생하고 있습니다! 해당 코드는 코드는 스택의 기본 개념을 이해하기 위한 학습용 구현이었기 때문에 그렇습니다. 실제로 이 코드는 O(N²) 시간 복잡도를 가져서 큰 입력값에서는 시간 초과가 발생할 수 있습니다!

따라서, 시간 복잡도를 개선하려면 다음과 같이 스택을 좀 더 효율적으로 활용할 수 있습니다

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

이 방식의 핵심 아이디어는 다음과 같습니다.

스택에 [인덱스, 높이]를 함께 저장하여 나중에 다시 순회할 필요를 없애기
현재 탑보다 작은 탑들은 스택에서 모두 제거 (어차피 앞으로도 쓸모없음)
남아있는 스택의 top이 수신 가능한 가장 가까운 탑

이렇게 하면 각 탑이 최대 한 번씩만 스택에 들어갔다 나오므로 O(N) 시간 복잡도로 문제를 해결할 수 있습니다. 이에 대한 풀이 방법은 추가적으로 문서에 서술해두도록 하겠습니다! 좋은 아이디어 주셔서 감사합니다 🙇

인프런 커뮤니티 질문&답변