[프로그래머스] 뒤에 있는 큰 수 찾기 (level2, python)

 

 

---

 

 

🤔 풀이 코드

from collections import deque

def solution(numbers):
    answer = [-1 for i in range(len(numbers))]
    stack = deque()
    
    for idx, now in enumerate(numbers):
        if not stack:
            stack.append([idx, now])
            continue
        
        top_idx, top_now = stack[-1]
        while stack and now > top_now:
            stack.pop()
            answer[top_idx] = now
            if stack:
                top_idx, top_now = stack[-1]
        
        stack.append([idx, now])
    
    return answer

 

🤔 문제 풀이

 

우선, 문제의 조건을 보면 numbers의 길이는 최대 100만입니다. 즉, 2중 for문을 사용해서 문제를 풀이하면 시간복잡도 측면에서 통과하지 못합니다.

 

이중 for문의 구현으로 보면, 현재 수를 선택하고 뒤의 모든 수와 비교해서 뒤 큰수를 찾는 식으로 구현할 수 있겠지만,

최악의 경우는 내림차순으로 정렬된 경우입니다.

[100만, 999999, 999998, ... 1]과 같은 예시가 있다면, 시간복잡도가 최고로 높은 연산을 하게 될 것입니다.

 

따라서 다른 방법을 찾아야 합니다.

제가 선택한 방법은 스택(Stack)을 활용하는 것입니다.

우선 result의 값을 모두 -1로 초기화 시킨 후, numbers의 숫자들에 대해 Stack에서 관리합니다.

스택에 넣는 수는 [현재 숫자의 인덱스, 현재 숫자]를 넣습니다.

 

스택이 비어있다면, 그냥 넣어줍니다.

스택이 비어있지 않다면, 스택의 top과 현재 값을 비교합니다. 현재 값이 더 크다면, 뒤 큰수에 해당하므로, pop 연산을 통해 스택의 내용을 꺼내고, 내용물이 가지고 있던 인덱스를 통해 result의 값을 현재 값으로 변경합니다.

이때, 깔려있던 원소에 대해서도 작용할 수 있기 때문에 while문으로 계속해서 비교합니다.

 

위와 같은 작업이 끝나면, 현재 숫자에 대해서도 뒤 큰수를 찾아야 하기 때문에 stack에 넣습니다.