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

해당 문제는 배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 찾는 문제다. 처음에는 이중 for문으로 문제를 풀게 되는데, 이 방식으로 접근하면 시간 초과가 발생한다.

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

 

다른 풀이 방식은 Stack으로 문제를 푸는 것이다. stack은 먼저 -1로 된 빈 공간을 생성한다. 그런 다음, while문을 조건으로 달 수 있다. while 문 안에 코드를 해석하면, stack[-1]로 된 부분은 이전 idx, 즉, idx-1 번째 값인 number[stack[-1]]과 다음 idx값 즉, number[idx] 값을 비교하고, 만약에 이전 값보다 다음 값이 큰 경우에는 idx-1 번째 값에 numbers[idx]를 입력하는 형태로 구성된다. 

def solution(numbers):
    stack = []
    answer = [-1] * len(numbers)
    for idx in range(len(numbers)):
        while stack and numbers[stack[-1]] < numbers[idx]:
            answer[stack.pop()] = numbers[idx]
        stack.append(idx)
    return answer