Programmers / 뒤에 있는 큰 수 찾기 / Python

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 뒤에 있는 큰 수 찾기 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

def solution(numbers):
    answer = []
    n = len(numbers)

    for i in range(n):
        for j in range(i, n):
            if numbers[i] < numbers[j]:
                answer.append(numbers[j])
                break
        if len(answer) < i + 1:
            answer.append(-1)

    return answer

 

처음 풀이는 시간 복잡도가 O(N^2)라서 틀렸다.

 

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

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

    return answer

 

두 번째 풀이는 스택은 아니지만 스택의 성질을 이용하여 큰 원소가 나오면 나머지 앞에 원소 인덱스에 큰 값을 넣었다.

이 경우에는 시간 복잡도는 O(N)이다.

---

※ 알아야 할 것

 

2단계 문제를 풀게 된다면 중첩 for문은 거의다 시간 초과가 뜬다.