[JAVA] [스택] Pro 뒤에 있는 큰 수 찾기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/154539?language=java 

프로그래머스

코드

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++){
            // 스택이 비어있지 않고 top이 numbers[i]보다 작으면
            // numbers[i]는 뒷 큰수이다
            while(!stack.isEmpty() && numbers[stack.peek()]<numbers[i]){
                answer[stack.pop()]=numbers[i];
            }
            stack.add(i);
        }
        return answer;
    }
}

시간복잡도

n=numbers.length
push, pop연산이 최대 2n번 발생하기 때문에 O(n)

 

어려웠던 부분

스택에 value말고 index도 넣을 수 있다는 걸 잊지말자