[코테 - py] 뒤에 있는 큰 수 찾기

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

프로그래머스

 

#  첫번째 푼 코드 - 시간초과

- 첫번째 코드는 기준 수보다 뒷 수를 순회하면서 가깝고 큰 수를 구하는 흐름으로 코드를 작성했다.

하지만 이렇게 하면 최악의 경우 O(n^2) 의 시간복잡도가 발생한다.

최대의 numbers의 길이가 1,000,000 이기 때문에 시간초과가 발생한다.

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

    return answer

 

 

# 두번째 푼 코드 - 성공

- 스택을 이용해서 풀었다. 이것의 시간복잡도는 O(n)이다.

def solution(numbers):
    result = [-1] * len(numbers)  # 결과 리스트를 -1로 초기화
    stack = []  # 인덱스를 저장할 스택

    for i in range(len(numbers)):
        # 스택이 비어있지 않고, 현재 숫자가 스택의 마지막 숫자보다 큰 경우
        while stack and numbers[stack[-1]] < numbers[i]:
            result[stack.pop()] = numbers[i]
        # 현재 인덱스를 스택에 추가
        stack.append(i)

    return result

 

 

- 이 문제는 스택에 대해서 배울 수 있었다. 한 달뒤에 다시 한번 풀어봐야겠다!