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

문제

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

풀이

풀이 1 - (시간초과)

1. numbers의 갯수와 동일하게 -1을 넣어 answer리스트를 만든다.
2. 이중 for문을 수행한다. 이때 첫번째 for문은 뒷 큰수를 찾는 수이다. 두번째 for문은 뒷 큰수가 될 가능성이 있는 수이다.
3. 뒷 큰수를 찾았을때 해당수를 answer에 업데이트하며 두번째 for문을 중단한다.

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

풀이 2 - (성공)

풀이1의 코드에서 시간 초과가 발생하는 이유는 중첩된 for 루프로 인해 시간 복잡도가 O(N^2)가 되기 때문입니다. 이렇게 두 개의 반복문을 사용하면 입력이 커질수록 실행 시간이 급격하게 증가하게 됩니다.

최적화된 방법은 스택(stack)을 활용하는 것입니다. 스택은 데이터를 임시로 저장하는 자료구조로, 나중에 차례대로 처리할 수 있도록 합니다. 스택을 사용하면 더 큰 수를 찾기 위해 이전의 숫자들을 저장해두었다가 나중에 사용할 수 있습니다.

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

    for i, num in enumerate(numbers):
        while stack and numbers[stack[-1]] < num:
            idx = stack.pop()
            answer[idx] = num
        stack.append(i)

    return answer

reference

• 스택(stack) 정리글