프로그래머스 - 뒤에 있는 큰 수 찾기(Python)

 문제 자체는 어렵지 않았다. 그저 자신의 뒤쪽에 가깝게 위치한 자신보다 큰 수를 찾는 문제이니 말이다.

2중 for문을 쓴다면 간단하겠지만 레벨 2쯤 되면 대충 봐도 이 방법은 시간 초과로 통과 못 할 게 뻔하다.

이에 나는 Stack을 활용하는 방안을 생각했다.

 

<풀이 방법>

1. 일단 answer에 -1을 채운다.
2. 누군가 들어갈 때 stack의 맨 위를 보면서 자신보다 작은 애들은 쫓아내고 자신의 값으로 덮어씌워준다.

 

바로 그냥 테스트 케이스 1로 보자면

 

stack : 2
answer : -1 -1 -1 -1

처음에 2는 자신보다 작은 친구가 존재하지 않기 때문에 무혈입성한다.

 

stack : 3
answer : 3 -1 -1 -1

이후 3 형님이 오면서 2는 쫓겨나고 3 형님을 세긴다.

 

stack : 3 3
answer : 3 -1 -1 -1

이후 3이 왔지만 둘은 친구이기 때문에 아무 일도 일어나지 않는다.

 

stack : 5
answer : 3 5 5 -1

이후 5 형님이 오면서 3은 쫓겨나고 5 형님을 세긴다. 

<문제>

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

 

---

<소스코드>

# 스택을 사용할 거임
# 일단 answer에 -1을 채운다.
# 누군가 들어갈 때 stack의 맨 위를 보면서 자신보다 작은 애들은 쫓아내고 자신의 값으로 덮어씌워준다.
def solution(numbers):
    answer = [-1] * len(numbers)
    stack = []
    
    for i in range(len(numbers)):
        while stack and numbers[stack[-1]] < numbers[i]:
            index = stack.pop()
            answer[index] = numbers[i]
        stack.append(i)
    
    return answer