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

문제

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

프로그래머스

[나의풀이 1번째] - 시간초과 실패

from collections import deque

def solution(numbers):
    answer = []
    dqList = deque(numbers)
    for i in list(dqList):
        dqList.popleft()
        isExist = False
        for j in list(dqList):
            if j > i:
                answer.append(j)
                isExist = True
                break
        if not isExist:
            answer.append(-1)
    return answer

[나의풀이 2번째] - 시간초과 실패

def solution(numbers):
    answer = []
    for i in range(len(numbers)):
        isExist = False
        for j in numbers[i+1:]:
            if j > numbers[i]:
                answer.append(j)
                isExist = True
                break
        if not isExist:
            answer.append(-1)
    return answer

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

문제 해석

• 정확이 어떤 알고리즘의 문제인지 몰랐는데, 스택문제 라고 한다.
• 자신보다 큰 수를 찾는 유형은 스택 유형인 경우가 많다고 한다.
• 순서대로 삽입하고, 조건에 충족한 수 (자기보다 큰 수)가 들어올 경우 스택을 비우면 된다.

문제 풀이

1. 스택에 순서대로 수를 삽입한다.
2. 스택 끝 수보다 큰 수가 들어오면 해당 위치에 큰 수를 대입하고 해당 스택을 비운다.
3. while 조건을 만족할 때 까지 순차적으로 스택을 비운다.

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