[Python] [Level 2] 뒤에 있는 큰 수 찾기 (stack 활용하기)

프로그래머스 문제

뒤에 있는 큰 수 찾기

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

프로그래머스

 

 

1차 풀이 (실패)

이중 loop로 만들면 너무 계산량이 많아서 시간 초과가 되어버린다

이중 loop로는 효율성 문제 때문에 통과 안되는거 같다.

"""
자신보다 뒤에서 크면서 가장 가까운 수 
"""
def solution(numbers):
    answer = []
    
    for i in range(len(numbers)):
        #print(numbers[i])
        
        for j in range(i+1, len(numbers)):
            #print(j)
            if numbers[j] > numbers[i]:
                answer.append(numbers[j])
                #print(numbers[j])
                break
            # 아무것도 없을 경우
            elif j == len(numbers)-1:
                answer.append(-1)
                #print(-1)
    
    # 맨 마지막은 그냥 -1
    answer.append(-1)
    return answer

 

 

뭔가 stack 형식으로 하면 풀린다고 한다는데 잘모르겠네

 

2차 풀이

솔직히 모르겠어서 답을 보고 말았다......

근데 답을 봐도 어렵다

1. answer에 일단 [-1, -1, -1, -1, ...]를 넣기
2. while문에서 numbers[stack[-1]]값과 numbers[i] 값과 비교, 
3. pop()을 해주어 뒷 큰 수가 없는 인덱스가 남도록 한다

 

"""
자신보다 뒤에서 크면서 가장 가까운 수 
"""
def solution(numbers):
    answer = [-1 for i in range(len(numbers))]
    stack = []
    
    for i in range(len(numbers)):
            # numbers[stack[-1]]는 앞의 번호, numbers[i] 뒤에 번호
            while stack and numbers[stack[-1]] < numbers[i]:
                answer[stack.pop()] = numbers[i]
            stack.append(i)
            print("answer =", answer)

    return answer