[알고리즘] 뒤에 있는 큰 수 찾기

Lv. 2

내 풀이 (시간 초과)

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

단순히 for문으로 풀었다.

효율적인 정답 풀이

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

    for i in range(len(numbers)):
        while stack and numbers[stack[-1]] < numbers[i]:  # stack의 top값이 현재 원소보다 작은 경우에는 stack에서 top값을 pop하여, 해당 원소의 뒷 큰수를 찾아서 answer에 추가
            answer[stack.pop()] = numbers[i]
        stack.append(i)
    return answer

stack을 사용하여 푼다. stack은 인덱스를 저장해두는 용도이다.

저장해둔 인덱스의 number와 현재 인덱스의 number를 비교하여 answer를 업데이트한다.

이제 난 stack을 활용할 수 있어야한다.

---

아래는 그저 나의 이해를 위한..

 

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges