[프로그래머스] 뒤에 있는 큰 수 찾기(Java), 스택 사용

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

프로그래머스

---

문제 풀이

numbers의 길이가 최대 1,000,000만이기 때문에 완전탐색 O(N^2)은 불가능하다.

-> 스택을 사용해야 한다는 것을 검색 후 깨달았다.

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Arrays.fill(answer, -1);
        
        Stack<Integer> stack = new Stack<>(); // 스택에는 인덱스를 보관
        
        for(int i=0; i<numbers.length; i++) {
            while(!stack.isEmpty() && numbers[i] > numbers[stack.peek()]) {
                // numbers[i] 값이 스택의 최상단 peek 값보다 크다면
                // 뒤에 있는 큰 수에 해당한다.
                answer[stack.pop()] = numbers[i];
            }
            stack.push(i);
        }
        return answer;
    }
}