[프로그래머스 - lv2] 뒤에 있는 큰 수 찾기 / 파이썬

 

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

 

---

문제 풀이)

스택의 LIFO(Last In First Out) 성질을 이용하여 해결할 수 있는 문제다.

스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 뒷큰수가 됩니다.

스택에 저장하는것은 수가 아닌 그 수의 인덱스를 저장한다는게 이 문제풀이의 핵심이었던것 같다.

 

아래 그림을 보면 문제 푸는 과정을 이해할 수 있다.

문제에서 예시에서 numbers = [2, 3, 3, 5]  인 경우를 생각해보자.

먼저 numbers 배열의 길이만큼 인덱스를 돌며 스택에서 작업을 한다.

처음에는 무조건 append를 하게 된다. 이때 배열의 인덱스를 stack에 append 해준다.

그 다음, numbers[0] < 3 이므로 stack의 인덱스를 pop함과 동시에 그 pop한 인덱스를 가지고 현재 number(=3)으로 answer 리스트를 업데이트 해준다. 그리고 현재 인덱스(=1)을 스택에 append시킨다.

다음 numbers[1] = 3이므로 pop 하는 과정없이 append 된다. 이후 numbers[1] < 5 이므로 stack에 남아있는 index 3, 2에 해당하는 값을 5로 업데이트 시킴과 동시에 pop한다.

마지막으로 스택에 없데이트 되지 못하고 남아있는 값들을 차례대로 pop해주며 -1로 업데이트 해주면 끝이다.(뒷큰수가 없는 수들은 스택에 남아있게됨)

 

정리하자면 다음과 같다.

1) 스택에 채워져 있거나 numbers[index] > numbers[top]인 경우 pop한 인덱스를 이용해 answer 리스트를 update 한다.

2) 현재 인덱스를 스택에 append하고 다음 인덱스로 넘어간다.

3) 스택에 남아 있는 인덱스 값을 -1로 업데이트 한다.

 

전체 코드는 다음과 같다.

def solution(numbers):
    answer = [0] * 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)
    while stack:
        answer[stack.pop()] = -1
    return answer