프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 시간초과 (일부 케이스 시간초과)

from collections import deque

def solution(numbers):
    answer = []
    
    max_num = max(numbers)
    length = len(numbers)
    numbers = deque(numbers)
    
    while numbers:
        
        v = numbers.popleft()
        res = -1
        
        if v==max_num:
            answer.append(res) 
            continue
            
        for num in numbers:
            if v<num:
                res = num
                break
        answer.append(res)    
        
    return answer

입력된 리스트의 요소별로, 현재 요소 뒤에 현재 요소보다 큰 요소가 있을 때 해당 값을 append하고 없다면 -1을 append하는 문제입니다.🐈🐈🐈

직관적으로 2중 for문을 활용하여 정답자체는 간단히 구현할 수 있지만 일부 케이스 시간초과가 걸렸습니다. 그리하여 deque로 선언하여 빠르게 popleft()하며 시간을 줄일 수 있었지만 여전히 3개 케이스에서 시간초과가 발생하였고 이를 해결하기 어려워 다른 풀이를 참고하였습니다.

[다른 사람의 풀이1]

def solution(numbers):
    answer = [-1]*len(numbers)
    
    stack = []
    
    for index in range(len(numbers)):
    
        target = numbers[index]
        
        while stack and numbers[stack[-1]]<target:
            answer[stack.pop()]=target
            
        stack.append(index)
                
    return answer

시간초과가 나는 2중 for문을 사용하지 않고 첫번째 for문에서 돌린 값들을 stack에 인덱스형태로 저장하여 비교하는 방식입니다.🐇🐇🐇

현재 요소(target)보다 이전 인덱스의 요소가 크다면, 이 큰 요소를 answer에 갱신하는 방식입니다.

for문 한번 시간복잡도를 이전 인덱스를 저장하는 stack으로 해결한 것이 포인트였습니다.

[다른 사람의 풀이2]

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

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

'다른 사람의 풀이1'과 같은 방식이되 answer를 산출해 낼 때, 현재 요소보다 큰 수가 있을 때는 미리 값을 갱신한 후 없을 때는 -1로 통일시켜 입력한 방식입니다.

감사합니다.