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

문제링크

문제 접근

• 이중 반복문 쓰면 시간초과
• DP로 해야하나??
• 해결 못하고 정답 확인 - 스텍 활용

코드

import java.util.*;
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Integer> stack = new Stack<>();
        
        for(int i=numbers.length-1;i>=0;i--){
            while(!stack.isEmpty()){
                if(stack.peek() > numbers[i]){
                    answer[i] = stack.peek();
                    break;
                }
                else stack.pop();    
            }
            if(stack.isEmpty()) answer[i] = -1;
            stack.push(numbers[i]);
        }
        return answer;
    }
}

결과

정리

• 스텍 문제인지 모르고 해맸다
• 완전탐색, bfs/dfs, DP, 스텍, 이분 탐색 정도는 다 생각해보자