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

문제

문제 설명

일단 프로그래머스는 시간제한이 따로 명시되어 있지 않다.
약 1~10초 정도의 시간 안에 풀면 된다고 암묵적으로 정해져 있다고 한다.
입력 N값이 최대 100만이므로, O(N^2)은 안된다.

IDEA (잘못된 생각들..)

일단 for문 두 개로 돌리는 방법은 절대 통하지 않는다. O(N^2)
그래서 뒤에서부터 하나씩 숫자들을 판단해가면서 dictionary에 최소 index를 저장해주고 탐색하는 식으로 가려고 했으나, dictionary에 저장되는 수마저 100만이므로 똑같이 O(N^2)가 되어 이 방법도 불가능하다.

IDEA - stack 자료구조 + while문

결국 아이디어를 참고하고 만 문제이다.😓
다음과 같이 하나씩 돌면서 numbers[i]가 '가까운 가장 큰 수'인  것들을 stack에서 뽑으면서 값을 할당하는 것이다.
그리고 stack에는 다시 index 값 i를 넣는다. -> 얘도 판단의 미로 속으로 들여보내는 것.! 나중에 stack에서 뽑히면 가장 가까운 큰 수가 할당될 예정이다.

뒤에 큰 수가 더이상 없는 경우들이 있을 때는 -1로 출력해주기로 했으므로 answer는 -1로 초기화시킨다.

def solution(numbers):
    stack = []
    answer = [-1] * len(numbers)
    for i in range(len(numbers)):
            while stack and numbers[stack[-1]] < numbers[i]:
                #print('아',stack)
                answer[stack.pop()] = numbers[i]
            stack.append(i)    
    return answer

백준에서 이 문제라고 한다. Lv2가 골드4 정도구나 싶었던 순간..
https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

시간복잡도

O(N)에 해당한다. 
시간복잡도 고려가 어려워서 stack을 사용하는 것을 떠올리기 어렵지만, 
이 문제를 곰곰이 생각해보면 또 stack만이 살 길이다! 싶은 생각이 들기도 한다..

일단 위에서 for문 안에 while문이 포함되어 있지만,
잘 생각해보면 for문은 N번 돌고, while문은 아무리 열심히 돌려봤자 각 요소들을 append 또는 pop시키는 일만 하기 때문에,
전체 루틴에서 while문은 최대 N번(append/pop을 고려해봤자 2N)밖에 돌지 않는다. 
(예를 들어 for문이 for i in range(4) 라면 그래봤자 1,2,1,1 이렇게 나눠서 총합은 N에 지나지 않는다.는 뜻이다.)
따라서 N+2N= 3N이 되므로 O(3N)이 최대 시간복잡도에 해당한다.