[프로그래머스/Python] 뒤에 있는 큰 수 찾기

📌 문제

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

📌 풀이

풀이 1 - (20~23번 테스트케이스 실패)

1. numbers길이와 동일한 리스트를 생성하는데 원소를 -1로 통일한다.
2. 이중 for문을 돌려 뒤에 있는 큰수를 찾는다.
   2-1. numbers[i]는 현재 숫자이며 numbers[j]는 뒤에 있는 숫자이다.
   2-2. number[j]가 numbers[i]보다 크면 answer[i]의 값을 number[j]로 바꾸면 for문을 중지한다.

def solution(numbers):
    answer = [-1 for _ in range(len(numbers))]
    
    for i in range(len(numbers)-1):  
        for j in range(i+1,len(numbers)):
            if numbers[i] < numbers[j]:
                answer[i] = numbers[j]
                break
                
    return answer

풀이 2 - (성공)

이전 코드는 두 개의 중첩된 반복문을 사용하기 때문에 입력이 커지면 시간 복잡도가 크게 증가할 수 있다. 특히 입력 리스트의 길이가 매우 큰 경우에는 시간 초과가 발생한다.

입력 리스트의 길이를 N이라고 하면, 첫 번째 반복문은 (N-1)번을 순회하며 두 번째 반복문은 최대 (N-1) + (N-2) + ... + 1 = N*(N-1)/2 번을 순회한다. 이로 인해 최악의 경우 시간 복잡도는 O(N^2)가 된다.

이제껏 리스트의 길이가 길어지는 경우 시간 초과가 나면 stack 구조를 이용하여 풀면 성공하는 경우가 매우 많았다.

def solution(numbers):
    answer = [-1] * len(numbers)  # 결과를 저장할 리스트
    stack = []  # 더 큰 값을 찾기 위한 스택
    
    for i in range(len(numbers)):
        while stack and numbers[stack[-1]] < numbers[i]:  # 스택이 비어있지 않고 현재 값이 스택의 맨 위 값보다 큰 경우
            last_index = stack.pop()  # 스택의 맨 위 값을 빼내고
            answer[last_index] = numbers[i]  # 해당 인덱스에 현재 값을 저장
        
        stack.append(i)  # 현재 값을 스택에 추가
    
    return answer