[프로그래머스] 뒤에 있는 큰수 찾기 (Python)

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

프로그래머스

 

 

시간 문제임.

 

문제 쉬운데 lv2인거 보고 알아차렸어야했는데, 

그냥 일단 해보자는 마음으로 했는데 시간초과 21,22 case에서 걸림ㅠ

 

나같은 사람을 위한 힌트

 

1. 앞에서 부터 했다면 뒤에서부터 답을 찾는다고 생각하기

2. stack 사용하기

 

 

이 힌트를 봐도 모르겠는사람은 아래 예시 참고해서 다시 해보셈

(예시)

numbers = [2, 7, 3, 5, 6, 1, 4, 8]\

8 (맨 오른쪽)	[8]	-1 (오른쪽에 더 큰 수 없음)
4	[8, 4]	8 (스택에서 4보다 큰 첫 번째 수)
1	[8, 4, 1]	4 (스택에서 1보다 큰 첫 번째 수)
6	[8, 6]	8 (스택에서 6보다 큰 첫 번째 수)
5	[8, 6, 5]	6 (스택에서 5보다 큰 첫 번째 수)
3	[8, 6, 5, 3]	5 (스택에서 3보다 큰 첫 번째 수)
7	[8, 7]	8 (스택에서 7보다 큰 첫 번째 수)
2	[8, 7, 2]	7 (스택에서 2보다 큰 첫 번째 수)

 

우선 첫시도 정석

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

 

 

 

2번째 시도 (힌트 적용)

# 2335
# 233  5 -1
# 23   53 5-1
# 2    53 55-1
#      532 355-1   

def solution(numbers):
    answer = []
    stack = []
    
    l = len(numbers)
    stack.append(numbers[-1])
    answer.append(-1)
    for i in range(l-2,-1,-1):
        while True:
            if stack:
                a = stack[-1]
                if numbers[i] < a:
                    answer.append(a)
                    stack.append(numbers[i])
                    break

                else:
                    stack.pop()
            else:
                answer.append(-1)
                stack.append(numbers[i])
                break
    
    ans = []
    for i in range(len(answer)):
        ans.append(answer.pop())
    
    return ans