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

https://school.programmers.co.kr/learn/courses/30/lessons/154539

시간 초과 코드

def solution(numbers):
    answer = []
    
    for i in range(len(numbers)):
        num = numbers[i]
        
        for j in range(i + 1, len(numbers)):
            if numbers[i] < numbers[j]:
                num = numbers[j]
                break
        
        if num == numbers[i]:
            num = -1
            
        answer.append(num)
                
    return answer

numbers의 길이가 100만이라 O(N^2)은 시간초과가 난다.

정답 코드

  def solution(numbers):
      answer = [-1] * len(numbers)

      stack = []

      for index in range(len(numbers)):

          now_num = numbers[index] # 현재 값

          while stack and numbers[stack[-1]] < now_num: # numbers[stack[-1]] -> 이전 값이 현재 값보다 큰 경우
              # 뒷 큰수로 판별해서 answer에 저장
              before_idx = stack.pop() # now -> 이전 인덱스 
              answer[before_idx] = now_num # now_num은 뒷 큰수

          stack.append(index) # 현재 인덱스를 스택에 저장

      return answer

• 인덱스를 스택에 저장하고 이전 인덱스로 이전 값을 가져오고 현재 값과 비교해서 뒷 큰수이면 answer에 저장한다.

참고
https://yinq.tistory.com/187