(Python/LV2)뒤에 있는 큰 수 찾기

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

풀이:

 

from collections import deque
def solution(numbers):

    res = []
    numbers = deque(numbers)
    while numbers:
        now = numbers.popleft()
        for i in numbers:
            if i > now:
                res.append(i)
                break
        else:
            res.append(-1)
    return res
    
    
82.6 / 100

 

for 문으로 앞에서 부터 계속하다보니 문제처럼 수가 많아지면 효율적이지않다.

 

 

def solution2(numbers):
    stack = []
    answer = [0] * len(numbers)

    for i in range(len(numbers)):
        while stack and numbers[stack[-1]] < numbers[i]:
            answer[stack.pop()] = numbers[i]
        stack.append(i)

    return [i if i != 0 else -1 for i in answer]

 

앞에서 부터 일단 담는데 그 다음에 숫자가 들어올때 비교를한다

만약 처음에 9가 들어오고 그 다음에 1이 들어오면

i = 0 일때 stack 비어 있으므로 while 문 패스   stack = [0] 

i = 1 일때 stack = [0] 이지만 옆에 숫자가 작으니깐 패스 stack = [0,1]

다음 i = 2 일때가 중요한데

stack = [0,1] 이 들어있고 numbers[stack[1]] 이 numbers[2] 보다 작으면 뒤에있는 큰 수 가 되는거다

ex) 

print(solution([9, 1, 5, 3, 6, 2]))

stack [0,1] 
numbers[stack[1]] = 1
numbers[2] = 5

그러면 더 큰수 위치에 최신화 시켜주고

담아있는 스택에 숫자랑도 더 큰수 인지 비교해서 넣어주면 된다

 

포문이 끝나면 

더큰수가 있는 수 빼고는 0 으로 채워져있다

컴프리핸션으로 0을 -1 로 바꿔준다.