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

프로그래머스 2레벨 문제이다.

문제 주소: https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

문제 해석

주어진 배열에서 가장 가까운 자기 자신보다 큰 수를 구하는 문제이다.

자신보다 큰 수가 없다면 -1을 반환하면 된다.

문제 풀이

자신보다 큰 수를 찾는 문제는 스택 유형인 경우가 많다.

순서대로 삽입되면서 조건에 충족한 수(자신보다 큰 수)가 들어오는 경우에 스택을 비우면 된다.

1. 스택에 순서대로 수를 삽입한다.
2. 스택 최상단의 수보다 큰 수가 들어오면 들어올 수보다 큰 수가 나오거나, 스택이 빌 때 까지 스택을 하나씩 pop 한다.
3. pop 하면서 해당 숫자의 index에 해당하는 값을 정답 갱신해준다.

스택이라는 문제 유형을 파악할 수 있다면 간단하게 풀 수 있다.

문제 코드

def solution(numbers):
    answer = [-1] * len(numbers)
    
    stack = []
    for i in range(len(numbers)):
        if not stack or numbers[i] <= stack[-1][1]:
            stack.append([i, numbers[i]])
        else:
            while stack and numbers[i] > stack[-1][1]:
                a, b = stack.pop()
                answer[a] = numbers[i]
            stack.append([i, numbers[i]])
        
    return answer

예제 결과