[프로그래머스|파이썬] 뒤에 있는 큰 수 찾기 (연습문제/lv.2)

문제

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

프로그래머스

 

 

🐍파이썬

❌ 실패 코드

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

이중 for문 사용

만약 numbers의 원소갯수가 1,000,000개이고 큰뒷수가 리스트의 끝에 존재한다면 999,999개를 비교해야 하므로 시간초과가 발생한다. 

def solution(numbers):
    answer = [-1 for _ in range(len(numbers))]
    stack = []
    for idx, num in enumerate(numbers):
        #스택에 원소가 남아있고 새로운 수가 스택상단의 수보다 크다면
        while stack and num > numbers[stack[-1]]:
            #answer 배열의 스택상단 idx 값에 큰 수 num 삽입
            answer[stack.pop()] = num
        #매번 stack에 새로운 수의 idx를 삽입
        stack.append(idx)
    return answer

 

💡 코드 설명

새로운 수(num)이 들어오면 numbers[스택 최상단 idx]값과 비교한다.

더 이상 새로운 수보다 작은 수가 없을 때까지 스택을 pop하고,

arr[pop한 스택 idx]에 새로운 수를 대입한다.

처음에 arr값을 모두 -1로 초기화했기 때문에 뒷 큰수를 찾지 못한 경우 -1 값이 그대로 유지된다.