[Python] 뒤에 있는 큰 수 찾기

✏️ 문제

 

문제 파악

처음엔 이중 for 반복문 사용했다가 numbers 길이가 1,000,000 까지라 시간복잡도에서 무조건 걸릴거라 예상했다..

그래서 배열을 한바퀴 돌되 그 전에 있던 값들도 비교를 하려면 stack에 넣어서 안의 값을 계속 비교하며 처리해야 할 것 같아 stack을 사용했다.

 

아직 stack을 잘 사용할 줄 모르는 거 같아서 큰일이다.. ㅠ

유사한 문제로는 주식가격이 있다.

 

코드

• 실패 코드

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

• 성공 코드

def solution(numbers):
    answer = [-1] * len(numbers) 
    stack = []

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

    return answer