[Programmers_Python] 뒤에 있는 큰 수 찾기

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

프로그래머스

내 풀이 방식 & 코드

 

 맨 앞에 있는 수부터 탐색해서 그 수보다 큰 수가 나오면 그 수를 answer에 넣고 break하고, 안나요면 -1을 넣는다. 그렇게 모든 수를 탐색하면 정답은 나온다. 하지만 이중 for문을 이용하다보니 시간초과가 나온다.

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

정답 코드

 stack 자료구조를 이용한다.

1. numbers의 길이만큼 반복한다.
2. stack에는 인덱스를 넣어준다.
3. 만약 스택의 마지막에 있는 인덱스에 해당하는 수(numbers[stack[-1]])가 현재 인덱스에 해당하는 수(numbers[i])보다 작으면 스택에서 인덱스를 하나 씩 pop해서 그 인덱스에 해당하는 인덱스의 answer에 number[i]를 넣는다.

 3에 해당하는 내용이 number[i]가 바로 뒤 큰 수를 의미하게 된다. 그래서 stack에서 인덱스를 하나씩 꺼내보면서 number[i]가 뒤 큰 수이면 해당 인덱스의 answer에 넣어준다. 그리고 뒤 큰 수를 못 구한 인덱스는 저장해 두고, 구하게 되면 그 인덱스는 없애야하기 때문에 stack 자료구조를 이용했다.

  

def solution(numbers):
    stack = []
    answer = [-1] * 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 answer

 

 내 풀이과정에서 시간초과가 나고 정답 풀이처럼 stack을 이용하면 되지 않을까해서 해봤지만 제대로 구현해내지 못했다,,, 그래서 다른분들의 정답 풀이를 참고해서 해결했지만 다음에 이러한 유형의 문제를 풀게되면 내가 해결할 수 있을지 의문이다,,