[프로그래머스] Python 뒤에 있는 큰 수 찾기 Level2 - 연습문제

문제 바로기기

접근 방법

범위가 상당히 넓기 때문에 일반적인 탐색법은 시간 초과에 걸린다.

0. -1 배열을 선언해 놓는다.
1. 뒤에 있는 수를 찾기 때문에 뒤에서 부터 순회한다.
2. stack에 현재보다 큰 숫자를 저장하여 앞으로 순회하여 비교한다.
3. 작거나 같은 숫자는 필요없기 때문에 버려준다.

시간초과 코드

def solution(numbers):
    answer = []

    for i in range(len(numbers) - 1):
        flag = False
        for j in range(i, len(numbers) - 1):
            if numbers[i] < numbers[j+1]:
                answer.append(numbers[j+1])
                flag = True
                break
        if not flag:
            answer.append(-1)

    answer.append(-1)
    return answer

정답 코드

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

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

    return answer