[구현-stack] 프로그래머스 뒤에 있는 큰 수 찾기(실패 분석 - 아이디어)

접근

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

문제는 쉬운데
시간 초과를 생각하고 풀어야합니다.
2중 for문을 돌면 시간초과가 날 수 있기 때문에
2중 for문을 돌더라도 완전탐색이 되지 않도록 하거나

혹은 stack을 이용해서 풀어야하는 문제입니다.

처음부터 2중 for문을 통해 풀 수 없는 문제라고 생각해서
stream()의 max()를 이용하려고 했으나
문제의 조건과 다른 값이 나와서 포기했습니다.
조건을 생각하려고 노력했는데 쉽게 떠오르지 않아 실패했습니다.

다른 분들의 풀이를 보고 Stack을 이용하면 풀 수 있겠다 생각했고
내부 클래스를 선언해서 위치와 값을 Stack에 함께 저장하는 방법을 생각해냈습니다.

그림으로 정리해보았습니다.
Stack에 처음 값은 무조건 넣고 시작합니다.

Stack 맨 위에 담겨진 값보다 들어오는 값이 크다면
꺼내서 그 값의 위치의 answer에 들어오는 값을 저장합니다.
꺼내고 그 다음 맨 위 값이 존재하면 또 비교해서 꺼내고
꺼낸 값의 위치의 answer에 들어오는 값을 비교합니다.

만약에 Stack 맨 위에 담겨진 값보다 들어오는 값이 작다면
아무런 일도 일어나지 않습니다.

이런 비교가 끝나면 들어오는 값을 Stack에 쌓습니다.

들어오려는 값이 더 이상 없을 때 Stack에 남겨진 값들이 있다면
이 값들은 뒤에 자신보다 큰 어떤 값도 없는 값들입니다.

따라서 하나씩 꺼내서 본인이 존재했던 위치의 answer에 -1을 저장합니다.

O(n)으로 가능하고 자신보다 큰 값이 등장하는 순간 Stack에서 pop되기 때문에 자신과 가장 가까운 큰 수를 구할 수 있습니다.

풀이

import java.util.*;

class Solution {
       static class Index{
            int index; //위치
            int value; //값
            public Index(int index, int value){
                this.index=index;
                this.value=value;
            }                       
        }
    public int[] solution(int[] numbers) {
        
        //정수로 이루어진 배열 numbers
        //자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이에 있는 수를 뒷 큰수
        // 모든 원소에 대한 뒷 큰수들을 차례대로 담은 배열을 return
        //뒷 큰수가 존재하지 않으면 -1
        
        
     
        int[] answer = new int[numbers.length];
        
        Stack<Index> stack = new Stack<>();
        
        //1. 처음 값은 넣기
        stack.push(new Index(0,numbers[0]));
        
        //2. 두번째 값부터 시작 
        for(int i=1;i<numbers.length;i++){
          
            //3. stack에 맨 윗 값이 numbers[i]보다 작으면
             while(stack.size()>0 && stack.peek().value<numbers[i]){
                //3-1. stack에서 꺼내고
                Index pop = stack.pop();
                 //3-2. 꺼낸 값의 index에 numbers[i] 저장
                answer[pop.index]=numbers[i];
             }
          
            // 4. numbers[i]는 무조건 넣는다.
            stack.push(new Index(i,numbers[i]));          
        }
        
        // 5. 마지막까지 stack에 남아있는 값들은 자신보다 큰 값이 뒤에 존재하지 않았기 때문에
        while(!stack.isEmpty()){
            //하나씩 꺼내서
            Index pop= stack.pop();
            //answer[본인이 위치했던 곳]=-1
            answer[pop.index]=-1;
        }
           
        return answer;
    } 
}