프로그래머스 - 뒤에 있는 큰 수 찾기

배열을 순회하면서 해당 배열의 요소를 기준으로 뒤의 요소들 중 나보다 큰 수를 먼저 만났을 때의 값을 출력하는 문제

 

조건을 보면 배열의 길이는 10^6이다.

 

단순하게 for문을 돌리고 해당 인덱스부터 다시 for문으로 검사하는 과정을 하면

시간복잡도는 O(N^2)

논리대로라면 1000000!를 계산해야해서 최악의 조건에서는 시간초과가 날 것이다.

 

정답을 도출해 내는 과정을 살펴보면

1. 나를 기준으로 뒤의 인덱스에서 나보다 큰 수 중 가장 가까운 수를 찾아내고

2. 있다면 해당 수가 정답이되고 없다면 -1이 된다.

 

가장 가까운 수를 찾는 것에서 stack을 쓰면 쉽게 할 수 있다는 것을 생각할 수 있다.

 

1. 스택을 마지막 수를 넣으며 선언하고 순회를 거꾸로 시작

-> 이유는 마지막 수의 정답은 항상 -1이다.

2. 스택에 값이 존재하고 나보다 큰 수가 스택의 가장 위에 존재할 때까지 스택을 pop해주는 것을 while문을 통해 반복

3. 해당 while문 종료 후

3-1. stack이 존재하면 스택의 가장 위의 수가 정답이 되고

3-2. stack이 존재하지 않으면 -1이 정답이 된다.

4. 이후 검사 중인 인덱스의 값을 stack에 추가한다!

 

def solution(numbers):
    answer = [-1 for i in range(len(numbers))]
    stack = [numbers[-1]]
    for i in range(len(numbers)-2, -1, -1):
        while stack and numbers[i] >= stack[-1]:
            stack.pop()
        else:
            if stack:
                answer[i] = stack[-1]
        stack.append(numbers[i])
        
        
    return answer