[Python] 프로그래머스 뒤에 있는 큰 수 찾기 풀이

문제 확인

프로그래머스

 

나의 풀이

• 완전 탐색으로 접근할 경우 $O(N^2)$ 이고, numbers의 길이는 최대 100만이기 때문에 시간 초과가 발생한다.
• 뒷 큰수는 앞에서 부터 값을 보관해 뒀다가, 더 큰 값이 나오면 제거하고, answer 정보를 업데이트하는 방식으로도 얻을 수 있다.
• 이 경우 스택에 값 numbers의 idx를 저장해두고, numbers의 숫자가 가장 최근에 입력된 값과 유사한 지 비교하면 된다. 

# 자신보다 뒤 + 크면서 가장 가까이 있는 수 : 뒷 큰수
# 뒷 큰수가 없으면 -1
# 완전 탐색 불가

# 큰 수가 없으면, 큰 수가 나올 때 까지 보관하고 확인해야 함
# 그러다가 큰 수가 나오면 바로 제거
# 스택을 활용해서 풀 수 있음

def solution(numbers):
    # 정답 정보
    answer = [-1] * len(numbers)
    # 스택
    stack = []
    for idx, num in enumerate(numbers):
        # 큰 수가 나온 경우, 그 수를 사용해 정답 정보 갱신
        while stack and numbers[stack[-1]] < num:
            answer[stack.pop()] = num
        stack.append(idx)
    
    return answer