오늘은 프로그래머스의 뒤에 있는 큰 수 찾기 문제를 풀어보았다.이 문제를 풀면서 처음으로 단조 스택(Monotonic Stack) 과NGE(Next Greater Element) 유형을 알게 됐다.처음에는 각 원소마다 오른쪽을 직접 탐색하면 될 것 같았지만,그렇게 하면 시간 복잡도가 O(N^2)라 시간 초과로 실패하기 때문에 다른 풀이가 필요하다.이 문제의 핵심은 스택으로 필요한 후보만 관리해서 O(N)에 해결하는 것이었다.나는 이 문제를 두 가지 방식으로 풀어보았다.앞에서부터 탐색 + 인덱스 스택뒤에서부터 탐색 + 값 스택NGE란?NGE는 Next Greater Element의 줄임말로,각 위치에서 오른쪽에 있으면서 처음 만나는 더 큰 수를 의미한다.따라서, 어떤 값의 오른쪽을 확인할 때 자기보다 큰 ..