Lv2. 뒤에 있는 큰 수 찾기

[뒤에 있는 큰 수 찾기]

문제 설명

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

제한사항

4 ≤ numbers의 길이 ≤ 1,000,000
1 ≤ numbers[i] ≤ 1,000,000

입출력 예

numbers	result
[2, 3, 3, 5]	[3, 5, 5, -1]
[9, 1, 5, 3, 6, 2]	[-1, 5, 6, 6, -1, -1]

---

내 코드

def solution(numbers):
    answer = []
    for num in numbers:
        idx = numbers.index(num)
        answer.append(bigger(num, numbers[idx+1:]))
    return answer

def bigger(std, numbers): #std for standard
    for num in numbers:
        if (std < num):
            return num
    return -1

brute force로 냅다 찾아버리는.. ㅋㅋㅋㅋ 그래서 O(n^2)이라 시간 초과로 통과못했다 자료구조를 써야한다는 건 이해했는데 어떤 자료구조를 써야할지는 생각을 못하겠더라 linked list? 이생각했다가 바로 접었고 ㅋㅋㅋ 쓰면 스택이나 큐를 쓰나? 했는데 어떻게 써야할지 감이 안잡혔다
포기하고 다른사람이 짠 코드를 봤는데도 이해가 안가서 고민중이다

다른사람 풀이

def solution(numbers):
    stack = [] # store the numbers which the next bigger number is not found
    answer = [0] * len(numbers) #initialize stack
    
    for i in range(len(numbers)):
        while stack and numbers[stack[-1]] < numbers[i]: 
        # while stack not empty and
        # while recent num from numbers(numbers indexed by top of the stack) is smaller 
        # than the next number from numbers
            answer[stack.pop()] = numbers[i]
            # stack.pop() = the next bigger number
    # for / while loop -> repeats until condition fails
        stack.append(i)
        # i-th number is not bigger than previous ones
        
    while stack:
        answer[stack.pop()] = -1
        # numbers in the stack = doesnt have bigger number :(
   
    return answer

손으로 적어가면서 주석 달고 손코딩 해보니까 약간 이해가 간다 음 이런 시스템으로 스택을 쓰는구나 싶은 정도의 이해?
그러나 나보고 이 문제 풀으라고 했을때 냅다 스택을 생각해내지는 못할 정도의 수준
그리고 사실 스택까지는 이해는 했는데 잠깐씩 어라 이게 왜..? 싶기도 한 걸 보니 아직 갈길이 멀다
완탐 말고 다른방법으로 구현하는 방식들을 좀 더 공부해둬야할 것 같다

다른 사람 풀이 2

from collections import defaultdict
def solution(numbers):
    answer = [-1]*len(numbers)
    for i in range(len(numbers)-1,-1,-1):
        for j in range(i-1,-1,-1):
            if numbers[j] >= numbers[i]:    break
            answer[j] = numbers[i]
    return answer

프로그래머스에서 긁어와서 출처는 딱히 없다 누구 코드라고 할 수 없는.. 출처를 달 수 없는 코드 ㅋㅋㅋ
처음에 접근했던 방식이랑 비슷한 것 같아서 긁어왔다 set이나 dictionary key로 했었는데 defaultdict import 가능한지 몰라서 안했다
아직 갈길이 멀다~~