[프로그래머스][스택] 뒤에 있는 큰 수

뒤에 있는 큰 수

 

• 첫 풀이
  • bisect을 사용해서 풀려고 했으나
  • 정렬된 리스트가 아니기 때문에 제대로된 idx 값을 뽑아내지 않아 오류 발생

from bisect import bisect_left
def solution(numbers):
    answer = []
    for i,num in enumerate(numbers):
        idx=bisect_left(numbers[i+1:], num+1)
        print(i,num,idx)
        if i+idx+1>=len(numbers):
            answer.append(-1)
        else:
            answer.append(numbers[i+idx+1])
    return answer

 

• 내 풀이 
  • stack으로 뒤에서부터 비교해서 해결하는 문제
    • stack의 마지막 값이 더 크면 해당값 answer에 삽입
    • 마지막값이 더 작으면 큰 값이 나올때까지 pop
      • 끝까지 큰 값이 없고 stack이 비면 answer에 -1 삽입하고
    • 현재 값 stack에 채워주기

def solution(numbers):
    stack=[]
    answer = []
    for num in numbers[::-1]:
        while True:
            if not stack:
                stack.append(num)
                answer.append(-1)
                break
            if num>=stack[-1]:
                stack.pop()
            else:
                answer.append(stack[-1])
                stack.append(num)
                break

    return answer[::-1]