뒤에 있는 큰 수 찾기(프로그래머스-연습문제)

문제

코드

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

풀이

(1) 아직 다음 큰 수를 찾지 못한 인덱스를 모아둘 index(Stack) 를 만들어주고, numbers 배열을 앞부분부터 하나씩 순회한다.
(2) 스택이 비어있거나, numbers[index.peek()]가 numbers[i] 보다 크면, 다음 큰 수를 찾지 못한 것이므로 index.push(i)를 해준다.
(3) 만약 numbers[index.peek()]가 numbers[i] 보다 작다면 다음 큰 수를 찾은 것이므로, answer[index.pop()]=numbers[i]가 된다. 이 과정을, index가 비지 않고, numbers[index.peek()]이 numbers[i] 보다 작을 때, 계속해서 반복해 준다.
(4) (3)의 과정이 멈춘다면, index.push(i)를 해준다.
(5) numbers의 모든 요소를 순회했음에도 index에 남아있는 요소들은 마지막까지 다음 큰 수를 찾지 못한 것이므로, -1을 넣어준다.

결과

제한사항을 보고 나서, 전부 비교하면 시간초과가 나겠구나 생각은 했다.
하지만 나는 greedy한 방법으로 시간을 조금 줄이는 방법 밖에는 생각이 나지 않았다. 내가 생각한 방법으로는 몇가지 테스트 케이스가 시간초과가 났다. 내가 생각한 방법은 끝까지 다음 큰 수를 찾지 못했던 수를 저장해두고, 이 수보다 크면 다음 큰 수를 찾아볼 필요도 없이 그냥 -1을 저장해버리는 것이다.

아무튼 시간초과가 나서 다시 생각을 해야 했는데, 도무지 생각이 나지않았다.
그래서 다른 사람 풀이를 참고했는데, stack을 사용해서 이렇게 풀 수 있다는 것은 정말 생각도 못했다.
하면 할수록 자신감이 떨어지는 것 같다.
왜 내 머리는 이런 방법이 떠오르지 않는걸까.
출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges