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

문제 링크:

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

회고:

• 이중 for문으로 풀게 되면 시간복잡도 O(N^2)이 되어서, 시간초과로 통과하기 어렵다.
• 스택으로 시간초과 해결
  • 스택을 사용하지 않고 각 원소의 뒷 큰수를 찾으려면, 모든 원소에 대해 나머지 모든 뒤쪽 원소와 비교해야 하므로 (2중 for문 필요) 시간 복잡도가 O(N^2)가 될 수 있다. 하지만 스택을 사용하면 각 원소는 최대 한 번씩만 스택에 push되고, 한 번씩만 pop 된다.
  • 스택에 numbers에 대한 인덱스를 저장하면서, 이미 뒷 큰수를 찾은 인덱스는 스택에서 제거하므로, 스택에는 처리해야 할 인덱스만 남게 된다. 마지막까지 스택에 남는 인덱스는 뒷 큰수를 찾지 못한 놈들만 남는다.

python

def solution(numbers):
    stack = []  # 자신보다 뒤에 큰 숫자가 없는 numbers의 인덱스만 stack에 남는다.
    result = [-1] * len(numbers)  # 초기 세팅

    for i in range(len(numbers)):
        while stack and numbers[stack[-1]] < numbers[i]:
            result[stack.pop()] = numbers[i]

        stack.append(i)

    return result

[-1, 5, 6, 6, -1, -1]